Consistency Conditions for Differentiable Surrogate Losses
Authors: Drona Khurana
Anish Thilagar
Dhamma Kimpara
Rafael Frongillo
Venue: NeurIPS 2025 poster ()
Keywords: Statistical consistency
surrogate loss functions
calibration
property elicitation
Primary area: theory
TL;DR: We present a practical characterization of statistical consistency for differentiable surrogate losses

Abstract: The statistical consistency of surrogate losses for discrete prediction tasks is often checked using the condition of calibration. However, directly verifying calibration can be arduous. Recent work shows that for polyhedral surrogates, a less arduous condition, indirect elicitation (IE), is still equivalent to calibration. We give the first results of this type for non-polyhedral surrogates, specifically the class of convex differentiable losses. We first prove that under mild conditions, IE and calibration are equivalent for one-dimensional losses in this class. We construct a counter-example that shows that this equivalence fails in higher dimensions. This motivates the introduction of strong IE, a strengthened form of IE that is equally easy to verify. We establish that strong IE implies calibration for differentiable surrogates and is both necessary and sufficient for strongly convex, differentiable surrogates. Finally, we apply these results to a range of problems to demonstrate the power of IE and strong IE for designing and analyzing consistent differentiable surrogates.

Consistency Conditions for Differentiable Surrogate Losses
Drona Khurana University of Colorado Boulder drona www.rana@cooooaaccc.......o.aaa. edu
Anish Thilagar University of Colorado Boulder anish@colorado edu
Dhamma Kimpara"
Rafael Frongillo
NSF National Center for Atmospheric Research Boulder, Colorado dkk ckimpara@ucar edu
University of Colorado Boulder raf@colorado.cm edu
Abstract
The statistical consistency of surrogate losses for discrete prediction tasks is often checked via the condition of calibration. However, directly verifying calibration can be arduous. Recent work shows that for polyhedral surrogates, less arduous condition, indirect elicitation (IE), is still equivalent to calibration. We give the first results of this type for non-polyhedral surrogates, specifically the class of convex differentiable losses. We first prove that under mild conditions, IE and calibration equivalent for one-dimensional losses in this class. We construct counter-example example that shows that this equivalence fails in higher dimensions. This motivates the introduction of strong IE, a strengthened form of IE that is equally easy to verify. We establish that strong IE implies calibration for differentiable surrogates and is both necessary and sufficient for strongly convex, differentiable surrogates. Finally, we apply these results to range of problems to demonstrate the power of IE and strong IE for designing and analyzing consistent differentiable surrogates.
counter-ee
1 Introduction
In supervised learning problems, the goal of the learner is to output a model that accurately predicts labels unseen feature vectors. These problems specified by target losses, metrics intended to reflect model error. Natural choices for target losses arise discrete prediction tasks like classification, ranking, and structured prediction. As minimizing discrete target losses directly is generally NP-hard, a convex surrogate loss is typically used instead. A link function maps surrogate reports (predictions) target reports. Beyond ease of optimization, the surrogate and link be statistically consistent with respect to the target loss, meaning that minimizing the surrogate should closely approximate minimizing the target given sufficient training data. In the finite-outcome outcome setting. consistency turns out to be equivalent to simpler condition called calibration [Bartlett et al., 2006, Tewari and Bartlett, 2007. Ramaswamy and Agarwal, 2016]. In particular, calibration has been central the design of new consistent surrogates, serving as the key condition which must be satisfied.
While simpler than consistency, directly verifying calibration is often cumbersome. In partieu- lar, calibration requires that all sequences of reports converging to the surrogate minimizers (i.e., minimizers of the expected surrogate loss), eventually link target minimizers (Figure 1), This complexity of verifying calibration in turn impedes the design of consistent surrogates. What easily
Work done while at University of Colorado Boulder.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Rd
Calibration
Indirect Elicitation
1
2 7(0)
Rd
1
r(p)
((P)
2
3
[(p) Kp).Ensurm additionally,
T(p), eventually link y(p).
Link [(p) p(p).
Notation: R surrogate reports; [(p)> surrogate minimizers; R- target reports; 7(p)= (2)- target minimizers; ş link
Figure 1: Calibration vs. Indirect Elicitation. Calibration requires surrogate minimizers, as well as all sequences converging to surrogate minimizers link to target minimizers. In general, is not trivial to choose a universal threshold past which the sequences link as desired. Determining such a threshold requires careful reasoning about the relative positions of surrogate minimizers across different outcome distributions, i.e., r(p) relative to [')) for y # p. IE is analytically easier to verify, as it only requires that surrogate minimizers link to target minimizers. Moreover, IE can be thought of as geometric condition on the probability simplex, which can directly lead to design insights ($44.
verifiable conditions still imply calibration for important classes of surrogate losses? One promising candidate is indirect elicitation (IE), which only requires that surrogate minimizers be linked to target minimizers (Figure 1). Finocchiaro al. [2019] established IE for polyhedral surrogates, which paved the way for the design of novel, consistent surrogates for several open target losses of interest [Wang and Scott, 2020, Thilagar et al., 2022, Finocchiaro et al., 2022b]. Whether or not this equivalence extends to other classes of surrogates has remained open. More generally, beyond the polyhedral case, we still lack simpler conditions for calibration that support the design of new surrogates, We give the first such results-IE-like conditions which are easier to verify than calibration for the broad and practically relevant class of convex, differentiable losses. We then demonstrate the power of these conditions to streamline the design process.
equivalence between calibration and
Theoretical Contributions. We first show that IE and calibration are equivalent for 1-d convex, differentiable losses ($ 3).2 In higher dimensions, however, IE no longer implies calibration, even for strongly convex surrogates (Example 2). To address this disparity, we propose a novel strengthening of IE we call strong indirect elicitation (strong IE; see Definition 6 in $ 3.4). Strong IE is as easy to verify as IE, as it only depends on surrogate minimizers and not on the surrounding sequences ($ 4.1). We prove that under mild technical assumptions, strong IE implies calibration for differentiable surrogates (Theorem 2). Moreover, for the important class of strongly convex, differentiable surrogates, we show that strong IE is both necessary and sufficient for calibration (Theorem 3). All our calibration proofs are constructive, providing explicit link functions as part of the argument. Taken together, our results deepen our understanding of the conditions required for statistical consistency of surtogate losses.
Significance for Design. We illustrate with two examples that proving IE or strong IE is strictly simpler than directly proving calibration, thus drastically shortening the pathway to establishing consistency ($4). We then demonstrate how the geometric insights from these simpler conditions enable the construction of consistent, 1-d differentiable surrogates for any orderable target loss (Theorem 4). As an application of Theorem 4, we construct novel 1-d surrogate that is convex, differentiable and consistent with respect to the ordinal regression loss. Together, these applications offer instructive proofs of concept and highlight how IE and strong IE can guide efficient surrogate design. We conclude with important future directions ($5).
Related Work. Previous works have also studied casier-to- verrify conditions that imply calibration for certain classes of surrogate losses; our work is unique in proposing conditions for arbitrary discrete targets that are broadly applicable to the class of differentiable surrogates. The first conditions for calibration were studied for the important case of multi-class classification, where the target loss the 0-1 loss. For binary classification, Bartlett al. [2006] study 1-d surrogates and show that these are calibrated if and only if the loss, in margin form (ayy), is differentiable at O and o' (0) < O. In multi-class classification, Tewari and Bartlett [2007] study higher dimensional surrogates with symmetric superprediction sets [Williamson and Cranko, 2023]. They establish a technical condition on these sets that allows for easier conditions for calibration such as ensuring that the optimizer sets are singletons. The first to formally study the relationship between IE and calibration were Agarwal and Agarwal [2015]. However, their results do not apply general discrete targets. For polyhedral
'The statement does not hold if one relaxes differeeniiabiityy see Example

---

losses, Ramaswamy and Agarwal [2016] showed that an IE-like condition is sufficient for calibration and Finocchiaro et al. [2024] showed that IE is equivalent to calibration for arbitrary discrete targets. Specific applications where IE influenced the design and analysis of surrogates/caliiration include Finocchiaro al. [2022b,a], Wang and Scott [2020], Nueve et al. [2024]. Our study of 1-d surrogates is heavily informed by the structure and elicitation of the target properties elucidated in Lambert et al. [2008], Lambert [2011], Steinwart et al. [2014], Finocchiaro and Frongillo [2018].
2 Background and Preliminaries
Symbol
Deseription
Symbol
Description
Y = [n]
Set of labels
R = [k]
Set of target reports
8: R R"
Discrete target loss function
L : R + R
Surrogate loss function
4. 12d R
Link function
A.
Probability simplex
7: A. =
Property elicited by L
r: A. R
Property elicited by L Level-set for at u
Level-set for y at
Table Summary of key notation
2.1 Targets, Surrogates and Link Functions
Given a finite label space y and finite report space R. let f. R. - RD be a discrete target loss associated with some prediction task. E()), represents the loss when the label is y y. Unless specified otherwise, we assume y = [n] and R = [k]. for n, k 2 2. We denote the probability simplex over y by An := {p E R" Rp 2 0, Vi E [n].p = 1}. As in Finocchiaro et al. [2020, 2024], assume that the target loss under consideration is non-redundant, i.e., every report r R uniquely minimizes the expected loss for some distribution, i.e., Vr E R, 3p E A, such that argmin,rext (p. {(r)) = (r).
Since is discrete and non-convex, it is hard to optimize. Our objective then, is to replace & with surrogate loss, defined over a continuous prediction space, say Rd Denote the surrogate by: 12 + _² For y E [n], let L(-), : Ra + K denote the 4 component of L. To enable optimization of the surrogate, L(.), Rd + R is convex for each y E y. Furthermore, since we are interested in analyzing differentiable surrogate losses, we will also assume that L(-), is differentiable for each y E V. For all our theoretical results, we will make the following assumption:
assume that each component of the surrogate is convex, i.e.,
Assumption 1. argmin L(u) is non-empty and compact for each y E [m]]
Within the class of differentiable functions, Assumption encompasses important range of aurroaates-including those with strongly convex components and strictly convex minimizable components. also covers more nuanced cases, such the surrogate described in Example 7 in Appendix A, which features two Huber-like components. Although each component is uniquely min- imizable, not all their convex combinations are. We demonstrate Section 4 that one-dimensional instantiation of this loss is calibrated with respect to the ordinal regression target loss.
As the objective is to minimize f, we must systematically map predictions in Id back to R. To do so, we introduce link function 10 : Rd + R.
2.2 Property Elicitation, Calibration and Indirect Elicitation
Any set-valued function defined on An is called property. We say a loss elicits a property, if it maps each distribution the minimizer of the expected loss under said distribution. We work with two key properties, denoted y and I, which we define below:
Definition 1 (Target Property, Elicits, Level Sets). The target loss e: R -> TR is said to elicit the property y : An = R, or in short-hand 7 := prop if
(p) = arg min(p, f(r))
PER
3

---

For any r E R. denote "/r S An as the level-set for at Le., == {p An/r 7(p)}. Since R a finite set, we say r a finite property.
Definition 2 (Surrogate Property, Elicits, Level Sets). The surrogale loss L Rd - R is said to elicit the property I A 3 IR, or in short-hand = prop LL] if
r(p) == arg min L(u)).
uER
For any u E Rd, denote r An as the level-set for I'a u, i.e., := : An/u E r())).
In order to ensure that surrogate-link pair is actually solving the target problem, we need to ensure that statistical consistency holds. In the finite outcome setting, it is well known that consistency reduces to the simpler notion of calibration [Bartlett et al., 2006, Tewari and Bartlett, 2007, Ra- maswamy and Agarwal, 2016]. We thus focus on calibration throughout this paper. Given some distribution An. and the corresponding surrogate minimizer(s) [(p). calibration roughly requires that all sequences of approximate minimizers link to the optimal target report.
Definition 3 (Calibration). Given a discrete target f, a surrogate-link pair (I,, 1) is calibrated if vp E A.:
inf (p, L(u)) > inf (p, L(u))
uER":o(u) (()))())))))))))))))))))
deRe
We also say L is calibrated, if there exists link v) such that (L, 1) is calibrated.
We next define indirect elicitation, condition even weaker than calibration (see Theorem 6 in Appendix B for a proof).
Definition 4 (Indirect Elicitation). A surrogate-link pair, (L, v)) indirectly elicits a discrete target & Yu E Rd, F. S Ye(ay- We also say L indirectly elicits E, Vu E RR,3r Br E R such that I S Yr-
For polyhedral surrogates, Finocchiaro et al. [2024] established that indirect elicitation and calibration are equivalent. This result is striking, as indirect elicitation is significantly easier to verify than calibration. The latter requires ensuring that, for each distribution p E An, any sequence of reports minimizing (p, L(-)) in the limit, eventually links to y(p). Equivalently, it demands that any sequence converging to I' I'(p) ultimately links to (p) (see Lemma 17 in Appendix C). In contrast, verifying indirect elicitation only necessitates linking optimal surrogate reports to optimal target reports. Specifically, if T,
0 for some report u then IE holds trivially and there nothing to check. Otherwise, if E [uu), IE demands that (u)) E 7p)). Thus, IE is fully determined by the structure of the minimizing reports, i.e., r(A,) == (T))lp E A.,, whereas calibration requires analyzing (pp) along with the local behavior of reports around it.
3 Motivating Counterexamples and Main Results
Our primary aim is to identify simpler conditions that yield calibration for differentiable surrogates. IE seems be an ideal candidate: it is substantially easier to verify, is known be equivalent for polyhedral losses, and all previously studied calibrated convex surrogates satisfy IF. However, not quite strong enough in general. We present two novel counterexamples (Example in 3.1, Example 2 in 3.3) that demonstrate why IE is insufficient for calibration. These examples are far from pathological, and thus demonstrate exactly why IE is too weak for this setting. Example motivates new condition, strong IE that we go onto show implies calibration for convex, differentiable surrogates, and is both necessary and sufficient if the surrogate has strongly convex components.
3.1 Indirect elicitation and calibration are not equivalent
All previously studied convex surrogates that are known to indirectly elicit a target loss are calibrated for some link function vb The literature has therefore treated both conditions as roughly equivalent to each other. Yet, this is not generally true. We identify the first known example of a loss that satisfies IE but cannot be calibrated for any choice of link function.
For example, consider the hinge surrogate for 0-1 loss, y = R- 1-1, 1) and L(u), = max(0, 1 uug)) ug). u u> 1. (L, x/) satisties IE but is not calibrated. However. if
If the link boundary is at u = 1, (u()) = the link boundary moved to O. then (L, v)) calibrated.

---

Expoctad Lows
Expested Lases
The expected loss for two surrogates for abstain loss. Left: Leusp a - (0.5.0.5), 0.5), is clear that no link yields calibration for the abstain target (Example 1). Right: [ammont) smoothed version of Leusp that is calibrated, again depicted at = (0.5, 0.5) (Example 6, Appendix A).
Figure 2:
Example 1 (Cusp). Let laks {-1. 1} + IR2 be the target loss for binary classification with abstain level using the label space [-11, [Bartlett and Wegkamp, 2008].
(0
r= 1/4 r= r= -
(rb((r)
Let Tupp R22 be the surrogate loss with Tecup (u)y y = (1 uy)2 |u]. and = sign(u) for + 0 and (0) (abstain). The expected loss of Leusp Ep [L))] at (0.5, 0.5) is plotted in Figure (left).
It is target-optimal to abstain whenever the most likely outcome occurs with probability of at most 3/4, i.e., 71 := {p D2 max(p1, P2] S 3/43 = {p E Aglp1 E [144,3 3/4]). J. Now, (Loup: 1b) indirectly elicits as Fo = T/L. Note that for any link to satisfy IE, it must agree with & in 0.5, 0.5]. However, calibration not satisfied for any Pı E (1/4,3/4), for example: sel p (0.5. 0.5). Consider any positive sequence (ut > 0)120 with + 0. Then, lim (p, uz) inf (p. M(u)). However, each u, links and never the correct report, 1. Indeed any link that satisfies IE exhibits this behavior (the sequence {ue} eventually links to 1). Thus, there is no other choice that could yield calibration. To restore calibration, suffices to "smooth out" the non-differentiable cusp at u O. to get differentiable surrogate in Figure 2. See Example 6 in Appendix A.
Leusp is remarkably simple non-polyhedral loss: is strongly convex, one-dimensional, and differentiable everywhere except for a single cusp at u 0. It is as 'nice' as non-differentiiabe loss can be. Yet, despite indirectly eliciting lats, it still fails satisfy calibration. Since smoothing out the cusp yields calibrated loss, natural question arises: does differentiability. combined with indirect elicitation, always imply calibration? Differentiable losses are well-structured and extensively studied in machine learning as they are optimization-ffrendly and enjoy fast convergence rates. This makes the question understanding the connection between IE and calibration under differentiability all the more compelling.
3.2 Differentiability and IE imply calibration for d =
In 1-dimension, answer the above question affirmatively: IE does imply calibration for differen- tiable real-valued surrogates. We provide a proof sketch of our theorem in this section.
To set the stage, we recall that target loss & that is indirectly elicited by 1-d surrogate (differentiable or not) possesses special structure. particular, Finocchiaro et al. [2020] showed that the property y := prop[4] [e] corresponding to such target satisfies condition known orderability, which roughly states that there exists a connected, 1-dimensional path that crosses each of the target level-sets.
Definition 5 (Orderable [Lambert, 2011)). A finite property An R is orderable. if there is an enumeration of R = {r1, r2,..., r such that for all S k 1, we have that Vir O Treea is hyperplane intersected with A..
Theorem 1. Let L R "R" be a convex, differentiable surrogate that indirectly elicits E, Under calibrated with respect to l.
Assumption
Proof sketch: We first show that for each j E [k 1), the boundary between adjacent target cells, i.e., Try Preza overlaps completely with some surrogate level-set. So, for some u' E I', Try Mirss
5

---

(0,1.0)
(0,1.0)
Eg
(0.1.0)
1/2,
1/20
Foun
(L.0.)
10.0.1) (L.000)
(0.0.1) (10.0)
15
(0.0.1)
Figure 3: Let 3 (1, 3). R - (1, Three candidate target losses l1 l2, fa R R that LCE (Example 2) could a surrogate for. For each i E {1, 2,3. ((1) (1,1,1). Whereas, (2( (5/2, 5/4, 0). (2(2) (2, 1,0 and (2 (5/3, 5/6, 0). The target boundary elicited by f (resp. (s) is the red line segment joining oi and of (resp. G3 and g²) The target boundary elicited by E2 the red line segment joining p and (0, 1,). The level sets of ICE are the blue points. All level sets of LEE are single points, barring (0,0)) which is the entire segment spanning from (1/2, 0, 1/2) to (0, 1/2, 1/2) (blue line segment). Left: no IE. The segment level set crosses the target boundary, so LcE cannot indirectly elicit fj. Center: IE. The segment level set does not cross, but just touches the target boundary, so IE holds, however, strong IE does not hold. Right: strong IE. The segment level set lies entirely within the target cell, so strong IE holds. Note: of (0, 0.8, 0.2), of (0.4, 0, 0.6), L = (0.2, 0.8, 0), d3 (0.6, 0, 0.4).
(Lemma 20). We then establish that for any two distributions p. E A,, that lie on either side of the target boundary Tr, O Try+1 optimal reports [p)). [gg) must lie on either side of u² (Lemma 21). Together, these results establish the existence of connected, 1-dimensional path through surrogate minimizers that faithfully mirrors any connected 1-dimensional path traversing the target level sets. This naturally induces a link z that tracks the paths by mapping w either of (ri, and mapping (p) and (4) r and rj+1 (Theorem 10).
The full proof and constructive link s are presented in Appendix D. It differs significantly from the polyhedral case, since barring convexity, differentiable and polyhedral losses have no commonality their underlying structure.
3.3 Differentiability and IE do not imply calibration for
Unfortunately, there is no direct analogue of Theorem 1 in higher dimensions. In particular, the following 2-dimensional surrogate is differentiable and satisfies IE for target, but is not calibrated.
Example 2 (Counterexample: IE without calibration). Ler y = {1, R = {1,2} } and consider LCE R22 R.Y, where
uf + u2 2u2
LCE(U)
2u + 01 + 2 + 2u2
3u3 u1 + u 2u2
Each component of LCF differentiable and strongly convex and LCE minimizable. LCE indirectly elicits the target lz R R23 shown in Figure (center, red). However, there is no link function 1b> TR2 R, such that the pair ( (I-Cr, 1b calibrated with respect to Ez. In particular, there exists sequence of reports that uniformly link to 1, but converge to (0, 0), which has to link to 2.
e/2). Then I(p=)= -
More formally, define for < <ESLp, ==
Notice that (ppc) (1) = (T())) = necessarily. Simultaneously, ((0.0) S. 72 and I (0.0) 7/, = (00 0)) 2. Denote p == 10,1/2,1/2) E ('0,,) and observe that ((p)) (2). Then, since Tpp)) (0.0) as < 0, follows by continuity that (p" LCe((Tp.))) (w", LCR((0, 0))) infneR= (p' L(u)). Thus, LeF violates calibration for any choice of link v.
Similarly Leusp the surrogate Les is extremely well-behaved. Each of its components are differen- tiable, strongly convex, minimizable, and the minimizing reports are always compact sets. Yet, LCR violates calibration despite satisfying IE with respect &2.
Turning our attention again to Figure (center), where level-sets are depicted in blue: we see that geometrically, the violation stems from the location of (0.0). where I' prop[LcE]- Every surrogate

---

level-set is a singleton, except I (0.0) (blue line segment). Notice that I' (0.0) just touches the (red) target boundary 71 n 7/ at the distribution (1/2, 0, 1/2). Shifting 71 n 72 to the right to get L immediately violates IE, since I' 2 7, for any r {1,2}. when y = p (Figure 3, left). On the other hand, shifting the boundary 7/1 72 by any amount to the left yields a target loss of form Ez, for which LCB is calibrated (Figure 3, right). So, while indirect elicitation requires that the segment level set be contained within Y2, calibration is only achieved for LCE when I ((000) is bounded away from the target boundary.
3.4 Strong indirect elicitation
Example 2 suggests that while calibration fails under IE, bounding the level set away from the target boundary resolves the problem. We formalize this idea with a new condition, strong indirect elicitation, which is strengthening of indirect elicitation (see Theorem 5 in Appendix B).
Definition 6 (Strong Indirect Elicitation). Given target loss l, let is =(p= T(p) S}. A surrogate L strongly indirectly elicits E vfu 3S C R such that Tu S 7/s; equivalently, for every u E Tdd and every p, 9 E Ta, 7(p) = (4))-
Revisiting Example 2: Notice that LCE does not satisfy strong IE with respect lz, since (P) = (1, while 7(00, 1/2)) = {2] and both p, 1/2, E [(0.0)- However, (p) - ((0, 1/2, 1/2)) = (2), when 7 = prop[[a]. Thus, LCE satisfies strong IE with respect to &..
Though close to IE in definition, strong IE turns out to be much more powerful for differentiable surrogates, in that it implies calibration."
Theorem 2. Let be a convex, differentiable surrogate that strongly indirectly elicits f. Under Assumption 1, L is calibrated with respect to f.
Proof sketch: Fix p E A. Key to our proof is establishing that the minimizers "surrounding" T(p) link to (p). Define the level-set bundle al p be the collection of all level-sets passing through p, i.e., T Tr(p) == Uu a. Repeated applications of strong IE establish the following: for a sufficiently small E, 0. the surrogate minimizers of distributions in 'ép-proximity'
the level-set bundle at p link to (p) (Lemma 29). For simplicity, denote this set of minimizers as the ey o--minmmizers. We have thus far that any valid link & must ensure that miiiimieii))))) 7p). By establishing upper- hemicontinuity of the set-valued map [()) Rd = R (Lemma 26), we show that for some 5p > 0 there exists neghhboboordo around [(p) wherein all minimizers are -p-minimizers (Lemma 27). Thus, all minimizers surrounding (pp) link to 7p). In effect, this means that surrogate minimizers that link different target reports are well-separated in space which is imperative for calibration. We conclude via an explicit construction to extend this link &b to a calibrated link defined for all surrogate reports, including the nowhere-optimal ones (Theorem 11). The reader may refer to Figure 7 in Appendix F for visual intuition of the proof.
Finally, we show that restricting to surrogates with strongly convex components makes strong IE necessary for calibration, and thus strong IE and calibration are equivalent for these surrogates.
Theorem 3. Let : Rdd -> R. be a surrogate, such that LQ:)- : R.d - lR is strongly convex and differentiable for each y E [n]. Then, I, is calibrated with respect to 8 if and only if it strongly indirectly elicits f.
Proof sketch: Strong convexity and differentiability together imply Assumption 1. The sufficiency of strong IE thus follows by Theorem 2. For necessity, we show that violating strong IE implies violating calibration. If IE is violated, calibration is violated immediately. So let assume we have IE but not strong IE. We show that under strong convexity, I' is continuous and single-valued (see Lemma 35 for proof). Next, we show the existence of report E Rd and a pair of distributions p, E T such that 7p)) C Cg)) (see Lemma 36). Thus, 3r E R. r E Eg)), however, r & (p). We then show that there exists a sequence of reports 9: + q. such that 7(g) = r. As I' is single-valued
there exists 24- = ). Vt. By continuity of I, qt + q = I(): ) + l(g) +
+ u. Further,
by the continuity of (p. L(-)), (p. L(ue)) + (p. L(u))
inf (p. L(v) since p E r w.- However, since r(q.) = { e u.) = r necessarily. At the same time, r & 7p). Hence, calibration is violated at p. See Theorem 12 in Appendix G for a full proof.
'Interestiigly, no polyhedral surrogate satisfies strong IE; see Theorem 7 in Appendix B
7

---

Applications
As IE and strong IE are easier to verify than calibration (Figure 1), our main results above lead to improved analytical methods to analyze and design consistent surrogates, which we now demonstrate.
4.1 Fase of verification
IE and strong IE are both completely characterized by the relation of optimal surrogate reports optimal target reports. Importantly, neither condition requires analyzing sequences converging to optimal reports. Thus both conditions are strictly simpler to verify than calibration. While strong IE is a more stringent requirement than IE, checking strong IE is just as casy as checking IE at the individual-report level (see Proposition in Appendix B).
We now present two examples illustrating how concluding calibration via IE or strong IE can significantly simplify the analysis: whereas direct calibration proofs require characterizing minimizers and analyzing nearby sequences, establishing IE or strong IE only requires reasoning about the minimizers themselves. (see also Figure for visual intuition)
Example 3 (Universally calibrated surrogate). Lemma 11 of Rumuswamy and Agarwal [2016] proposes a - 1-dimensional, strongly convex, differentiable surrogate that is calibrated for all discrete targets. After the first claim in their proof (see pages 29-30 Ramaswamy and Agarwal [2016]):
Proof via strong IE
Fix An. Minimizing (p, L(u)) = Σj= (p,(u, 1)² + (1 -P))3)) yields the unique
minimizer u² (P1..... Pn-1) Hence [(p) - and r,, {p}. Immediately, L satisfies strong IE, and thus is calibrated by Theorem 2.
Our approach shortens the proof from an entire page to sew lines. We also obviate the need for subtle arguments regarding the convergence of sequences that were required in the original proof.
Example (Subset-ranking surrogates). Theorem 3 of Ramaswamy et [2013] proposes a low- dimensional calibrated surrogate for subset-ranking largets common in information retrieval. Our results significantly shorten their calibration proof (see pages 3-4, Ramaswamy et al. [2013]):
Proof via strong IE
The surrogate is strongly convex and differentiable, so strong HE suffices for calibration. Pick any Ed and any p, q E Fu. To prove strong IE, suffices to show that 7(p) 7q)). u is the unique minimizer for L()) and (q, L(-)) + (+) up =u= = u. By line of page 4, p = (uP) B, + Similarly, q Th (u G, + c. By (+), 14 =0 q for any t T (target reports). Thus, argmin
argmin lu So, 7()) 7()).
This bypasses all subsequent proof steps (25 lines) following the first line of page 4 wherein intricate reasoning to show all sequences converging to minimizer sets are appropriately linked.
4.2 Design of 1-dimensional surrogates
Example 3 demonstrates the existence of an dimensional surrogate that is calibrated for any target loss with outcomes. However, the complexity of several optimization algorithms often linear, or even quadratic in the domain dimension. Thus, major research goal of the surrogate for large n) when loss literature the design of dimension-effiiient surrogates (ideally d <<< Finocchiaro et al., 2019, possible [Ramaswamy and Agarwal, 2012, Ramaswamy et al., 2013, 2015, Blondel, 2019, Finocchiaro al., 2021]. Recall that Theorem established the equivalence between IE and calibration for 1-d differentiable surrogates. This equivalence enables us to construct 1-d surrogate that convex and differentiable, for any orderable target loss. We formalize this statement below in Theorem 4 and provide proof sketch that highlights the key ideas behind the construction.
Theorem 4, Given an orderable target i R + R", there exists a convex, differentiable surrogate L g. satisfying Assumption which is calibrated with respect é.
8

---

18300
71
733
13.000
13/2.0372)
09.0.1
Figure 4: Let Lety== R (1. The solid-peachs colored lines depict the target boundaries elicited by the ordinal regression loss gndd R + R2. The dotted-blue lines depict the level-sets of the surrogate Lu - R defined Example 5. Since no level-set LH R crosses from one target cell to another, IE holds. By Theorem I calibration follows.
Proof' sketch. Since y = prop[{] is orderable, there is an orderable enumeration (fi,...: F' of reports (Def. 5). By Theorem 11 of Finocchiaro et al. [2020], there exist vectors U1...., 0k IR" such that (i) for each j E [k 1]. (p, 02) 0 for all p E Yry O 7r511 and (ii) the coordinates are monotone, i.., V1yy S 1/+1.y for every E jk - 2] and y E [n].
Let V ( have columns 01...., .k-1, and write V for the j-th row. For each j E [n]. define L(-); = LinIntGrac(V")) (Subroutine 1, Appendix H). The subroutine first specifies
map 9; - on |1, by linear interpolation of the values ["[1]...., V 1], so that
(i) [i[i] for all integers i E fl....,k k- 1}: hence 9j is continuous and nondecrcasing on k 1]. In particular, for 1, (x) X[]] + (x 1).
(1, 1). It then extends 9j outside [1,
And for 2 1 [z(x) X|k 1] (xr (k- 1)). The construction ensures that continuity and monotonicity of 93 are preserved across IR. Furthermore, 93 crosses 0 either at singleton, or at compact interval. Finally, the subroutine sets L(u); = fi (t) dt, (L(),) 9j. Lemma 37 proves that each I(-); is convex, belongs (R)) has nonempty compact minimizers (the sets (0)lū E [m]}), and so satisfies Assumption Moreover, at integers E (l,...,A: 1} we have L() = U4. In Theorem 13 of Appendix H. we show that these properties imply L indirectly elicits l. Hence L is calibrated with respect to & by Theorem 1.
As application of Theorem 4, present novel surrogate for the ordinal regression target loss in Example 5. While previous works have proposed surrogates for ordinal regression [Ramaswamy and Agarwal, 2016, Pedregosa al., 2017, Finocchiaro et al., 2019], none the surrogates therein simultaneously convex, differentiable, minimizable and I-dimensional.
Example 5 (Huber-like surrogate for ordinal regression). Here = - Predictions farther away from the true outcome are more heavily penalized. The 3-class ordinal regression loss (ord(y, r) = - rr, for y, E (1,2,3) Then an application of Theorem 4 yields the surrogate
Lu IR + RR Lu(x) [f(x 2), h(x) f(x 2)).
where h(z) =² and f(x) - - -
and f(x) |z| 0.5 otherwise.
LH indirectly elicits gard and is therefore calibrated with respect to it. Figure 4 depicts the target (peach colored lines) and surrogate (blue dotted lines) level-sets for gord and Lup The target good poses non-trivial challenge. In particular, for 1-d convex, differentiable surrogate L to indirectly elicit good must admit non-uniee non-unique minimizer at (0, 1/2,0) since the two target- boundaries intersect at this point. On the other hand, the minimizers elsewhere must be unique. Lu is precisely such minimizer. For Ln. (((1/2,0,1/2) = 11, whereas for every other p E Ag. [[()]] =I
Discussion and Future Directions
Our results are the first to establish general calibration conditions on the widely used class convex differentiable surrogate losses in relation to arbitrary discrete target losses. We anticipate that the generality of our results will aid further advances in application and theory. Our conditions are inspired by the equivalence of IE and calibration for polyhedral surrogates. Like IE, strong IE is

---

substantially easier to verify than checking calibration directly. Hence, strong IE for differentiable losses could play a similar role IE for polyhedral losses, where IE has been used establish convex calibration dimension bounds [Ramaswamy and Agarwal, 2016] and to design and analyze numerous surrogates [Finocchiaro et al., 2022b,a, Wang and Scott, 2020, Nueve al., 2024]. Indeed, we already make first steps in regards to design, by proposing generalized construction for designing differentiable I-dimensional surrogates for orderable targets.
Lower bounds. A promising direction for future work is to strong IE study prediction dimension. We believe it can establish lower bounds on the prediction dimension of calibrated surrogates for important target losses. Finocchiaro al. [2021] leverage IE as a tool establish such lower bounds. Recall that strong IE is necessary for calibration for the class of strongly convex, differentiable surrogate. At the same time, strong IE imposes more stringent constraints on surrogates than IE, We therefore believe strong IE offers promise to establish novel lower bounds in this setting.
Relaxing Assumption 1. Theorems and 2 assume that arg min L()) is non-empty and compact for each y [na]. Theorem 8 in Appendix C shows that Assumption I is equivalent to the condition that l'(p) non-empty and compact for every p E An. The non-emptiness, i.c., minimizability of the functions L())) p E A,) is mathematically well-motivated. Indeed, if minimizability fails for some distribution p E A., then r(p) is empty. In this case, checking calibration p necessitates analyzing sequences of form {u, JeeN, such that lim (p. L(w))) infueR= (p. L(u)). Thus, while understanding calibration for non-minimizable losses is an important and interesting direction in its own right, IE and strong IE are not the appropriate tools to do so. We speculate instead that the recently developed theory on astral spaces [Dudík et al., 2022] can be leveraged for this direction. Our assumption of compactness on [(p) is technical and necessary for our proof approach, but may not be strictly necessary for strong IE to yield calibration. Differentiable surrogates with unbounded (and thus non-compact) minimizers are common in practice (for example: the squared hinge loss, the modified Huber loss, etc.) Relaxing this assumption is therefore a valuable direction for future research and could potentially enhance the practical appeal of strong IE.
Acknowledgments and Disclosure of Funding
We thank Mabel Cluff for early discussions and insights on this project. We thank Stephen Becker for discussions on convergence properties of set-valued functions. We thank Jessie Finocchiaro and Enrique Nueve for discussions on 1 surrogate losses. This material is based upon work supported by the National Science Foundation under Grant No. 11S-2045347.
References
A. Agarwal and S. Agarwal. On consistent surrogate risk minimization and property elicitation. In Conference on Learning Theory, pages 4-22. PMLR, 2015. 2
F. Aurenhammer. Power diagrams: properties, algorithms and applications. SIAM journal on computing, 16(1):78-96, 1987. 15
L. Bartlett and M. H. Wegkamp. Classification with a reject option using a hinge loss. Journal of Machine Learning Research, 98), 2008. 5
L. Bartlett, M. Jordan, and J. D. McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 141(4)3: 156, 2006. 1, 2,
M. Blondel. Structured prediction with projection oracles. Advances neural information processing systems, 32, 2019. 8
K. C. Border. Introduction to correspondences, 2013. 21, 22
S. Boyd. Convex optimization. Cambridge UP, 2004. 26
M. Dudík, R. F. Schapire, and M. Telgarsky. Convex analysis at infinity: An introduction to astral space. arXiv preprint w2xiv:2205.032660 2022. 10
10

---

J. Finocchiaro and R. Frongillo. Convex elicitation of continuous properties. Advances in Neural Information Processing Systems, 31, 2018.
J. Finocchiaro, R. Frongillo, and B. Waggoner. An embedding framework for consistent polyhedral
surrogates. Advances in neural information processing systems, 32, 2019. 2, 8,
Finocchiaro, Frongillo, and B. Waggoner. Embedding dimension of polyhedral losses. In
Conference Learning Theory, pages 1538-1585. PMLR, 2020. 3, 9, 19, 30
J. Finocchiaro, R. Frongillo, and B. Waggoner. Unifying lower bounds prediction dimension of convex surrogates. Advances in Neural Information Processing Systems, 34:22046-22057, 2021.
8. 10
Finocchiaro, R. M. Frongillo, and B. Waggoner. An embedding framework for the design and analysis of consistent polyhedral surrogates. Journal of Machine Learning Research, 25(63):1-60, 2024. 3, 4, 14
J. J. Finocchiaro, R. Frongillo, E. Goodwill, and A. Thilagar. Consistent polyhedral surrogates for top-k classification and variants. In International Conference on Machine Learning, pages 21329 21359. PMLR, 2022a. 3, 10
J. J. Finocchiaro, R. Frongillo, and E. B. Nueve. The structured abstain problem and the lovász hinge. In Conference on Learning Theory, pages 9718-3740. PMLR, 2022b. 2, 3, 10
M. Henk, J. Richter-Gebert, and G. M. Ziegler. Basic properties of convex polytopes. In Handbook of discrete and computational geometry, pages 383-413. Chapman and Hall/CRC, 2017.
J. Hiriart-Urrury and C. Lemaréchal. Convex analysis and minimization algorithms I: Fundamen- tals, volume 305. Springer science & business media, 1996. 16
S.-T. Hu. Introduction to general topology. (No Title), 1966. 22
N. S. Lambert. Elicitation and evaluation of statistical forecasts. Preprint, 2011. 1. 3, 5, 18
N. S. Lambert, D. M. Pennock, and Y. Shoham. Eliciting properties of probability distributions. In Proceedings of the 9th ACM Conference on Electronic Commerce, pages 129-138, 2008. 3, 15
E. Nueve, D. Kimpara, B. Waggoner, and J. Finocchiaro. Trading off consistency and dimensionality of convex surrogates for multiclass classification. In Advances in Neural Information Processing Systems, 2024. 3, 10
F. Pedregosa. F. Bach, and A. Gramfort. On the consistency of ordinal regression methods. Journal of Machine Learning Research, 18(55):1-35, 2017. 9
H. G. Ramaswamy and S. Agarwal. Classification calibration dimension for general multiclass losses. Advances in Neural Information Processing Systems, 25, 2012.
H. G. Ramaswamy and S. Agarwal. Convex calibration dimension for multiclass loss matrices. Journal of Machine Learning Research, 17(14):1-45, 2016. 1, 3, 4, 8, 9, 10
H. G. Ramaswamy, S. Agarwal, and A. Tewari. Convex calibrated surrogates for low-rank loss matrices with applications to subset ranking losses. Advances in Neural Information Processing Systems, 26, 2013.
H. G. Ramaswamy, A. Tewari, and S. Agarwal. Consistent algorithms for multiclass classification with reject option. arXiv preprint arXiv:1505.04133 2015. 8
R. Rockafellar. Convex analysis. Princeton Mathematical Series, 28, 1970.
I. Steinwart, C. Pasin, R. Williamson, and S. Zhang. Elicitation and identification of properties. In Conference Learning Theory, pages 482-526. PMLR, 2014. 3
A. Tewari and Bartlett. On the consistency of multiclass classification methods. Journal of Machine Learning Research, 8(5), 2007. 1,

---

A. Thilagar, R. Frongillo. J. J. Finocchiaro, and E. Goodwill. Consistent polyhedral surrogates for top-k classification and variants. In International Conference on Machine Learning, pages 21329-21359, PMLR, 2022. 2
Y. Wang and C. Scott. Weston-watkins hinge loss and ordered partitions. Advances in neural information processing systems, 33:19873-19988 2020. 2, 3, 10
R. C. Williamson and Z. Cranko. The geometry and calculus of losses. Journal of Machine Learning Research, 24(342):1-72, 2023. 2
A Examples
[1 11-1822 bi (1-ap
2
1-
(x)
Figure 5: The figure on the left plots the superprediction set, (L(u) u E RR+,, of a surrogate loss that IEs but is not calibrated. To see non-calibration, notice that there only one possible link. Fix = [0.5, 0.5] The optimal loss is achieved by arg inf ( (u, p). Thus the loss is optimized by v which must link to the abstain report L. However, consider the points to the left of vi, which link +1. The infimum of the loss over these points for p is equal to the loss v. thus violating calibration.
Example 6. Let the target loss be binary classification with abstain level 1. Lymooth IR + R?
Lymooth ( (u)y == (1 - uy))
This the smooth loss plotted on the right side of Figure 5. For any p E [0. 1], I'(p, 1- 1-p))
Hence T., = ((- }-)) Clearly, each component of T.mmooh is strongly convex and differentiable. by Theorem
Thus, if Lmmooth strongly indirectly elicits E, then Tsmooth calibrated with respect 3. Since T,, is a singleton, strong IE follows trivially by definition, and so Lsmook is calibrated with respect to E. "Smoothening out" Lewop from Example 1 thus resolves calibration.
Example 7 (Convex Combinations of Huber losses). For E Rd, let
||u/|2 1
||u|12 2
fH(
2
||u||2 I 1
be the Huber loss in Rdd Define
fH(U + (2,0 .2.0......)) fu(uu - (2,0. 0. 033)
[u)
be the sum of two Huber losses. Then, for = 1/2, I(p) = 1- [0) For > 1/2, r(p) is
a single point (1, 2) x {0)d-1, For p < 1/2, Tpp) is a single point in 1-2,- -1) 1) x (0) We can this visually for d = 1 in Figure 6.
12

---

Figure 6: The plot of (p, L (u)) for 3 different values of p with d In higher dimensions, the loss is minimized by exactly the same points, since by construction the minima will always lie on the U1 ui-ax.s. Left: p 1/4, the (p. (u)) has unique minimum
-5/3. Center: p= 1/2, the (p, Lu (u)) is minimized by any choice of E [-1,1]. Left: 3/4, 4, the (p, Lu (u)) has a unique minimum at a = 5/3.
Lemma 1. vank(VI<cr(u)) is when = (0, 0) and 2 otherwise.
Proof.
22m 2u2 + 2
VCC((u) =
4u1
+
4ug + 2
68i
2u2
Let in and 02 denote the first and second column of V LCr((u) respectively. Pank(VLertl 0 and only if 01 82 O. However, there is no choice of ij u2 such that either v1 02 are 0, so Lank(V 2 everywhere.
= 1 if and only if λo = for some E R. For this to hold for the first row of (Cc((u) we must have 2 + À = 2uz + so u2 = Au1 + - 1. Similarly, using the second row of LCE(u)) implies W2 Au + 1/ 3.2 This gives two equivalent expressions for u2, so must have
1. so A 2. Plugging this into either of the expressions for u2 yields U2 2u1-
Finally, using these values of À and U2 the last row of VCCE(U) becomes 12u, 2 = 4uj - 2, so as well. Therefore, rank( Monk(VLce (CE(()))))
U1 0, and thus U2 2u,
only when u (0,0).
For any other value of u, we then have rank Len ) 2 2, but since u E RR?, vank((V $ everywhere. Therefore, for all u + (0, rank (w) = 2.
B Property Elicitation, Level Sets and Minimizing Sets
Lemma 2. Let B, A. A B. Then I(A) CT(
Proof. Since A C B, we have that Va E A, E B. So, Va E A,T(a) S Ub) = I(B). Thus, T(A) ((a) ((B)
Lemma 3. Consider any convex, differentiable Rd + R" Let p E An and u E Rd. Then, LETT l'pp) = V((u) p Og. Equivalently, I., = {p C (L)uV(())) p 0a).
Proof. Since Try is convex for every y E [n). it follows that the function (p. I.-)) Rd R is convex
for any E A.. Now, since the domain of (p. I(.)) is open and the minimum is attained at some
u E Rdd it follows that V (p, L(w)) = O₂ = V((u) = Oz- Conversely, V (p, L(w)) = Oa- then r(p) by convexity of (p. L(-)).
O
Lemma 4. Any convex, differentiable surrogate L : Rd - R that indirectly elicits target R Rd satisfies rank(V (V)) > 0 for every Rdd
Proof. Assume to the contrary, i.e., 3u E Rd such that, rank (LL())T O. By the rank-nullity theorem, this means mull( [ Lemma we get that r, = A,, We assume so (1,2) C R for any problem of interest. First consider the pair of discrete reports (1, 2). By the non-redundancy of discrete reports, 7pI E 7.P2 E 72. such that (p1, E(-)) is uniquely optimized by the discrete prediction 1 and (p2, {(-) is uniquely optimized by the discrete prediction 2. Since
So VL(u) p O₂ is satisfied by any p E A,, From
RI 2 If not, the prediction problem trivial,
13

---

T. = An, it follows that P1.P2 E Tu. This means Tu & 71. since p2 & n. and similarly Tu I 72- Similarly, for any j E R : & {1, 2,, consider the reports (1,j) and repeat the same rationale to establish that To _ Tt. Thus, Eu E IR such that I' & Yr. Vr E R, implying L does not indirectly clicit e by the definition of indirect elicitation.
Lemma 5. Let L: R - IR be a convex, but not necessarily differentiable surrogate. Then for any R. Tu is compact.
Proof. Pick any E IR. Since r. S A. and A, is compact, it is clear that I is bounded. So it suffices to show that T is closed. Let {pt heR, Tru and suppose that P. - p. We want to show that p E r.. First note that since Pr E An for each t, it follows that p A., by compactness of A.. Now, pick any v E R. It holds for each t E N+ that (pe, L(u)) I L()).. Taking the limit as + oo on both sides, it holds that (p, I(u)) S (p, L(v) for any u E RR.. Thus, u E T()) = p E T Hence, T. is closed.
Theorem 5. Let L Rd - RR" be surrogate that strongly indirectly elicits a target loss L R. + R Then L indirectly elicits f.
Proof. Pick any Rd. By definition, there exists some S C R. such that 7(p) S for every
P E T.. Equivalently, E DresTr for every E T.. Thus, F. S NresTr = Er E R, such that T. Tr.
Theorem Let L: IR R" be a surrogate that is calibrated with respect é: R + R" Then L indirectly elicits f.
Proof. Since L is calibrated with respect to f, there exists a link function き Rd + R. such that, (I, +) is calibrated with respect to f. Suppose E Rd If I(A,), then r, 1 = T. S %
Vr E R yielding indirect elicitation. Now, suppose u E I(An). We show that Ia S No(u)- Assume to the contrary. Then, there exists some p E Pu.. such that p & 7e(u) = vi(u) & 7P))
Then, (nf (p, I(V)) S (p, L(u)) = inf (p, [(w)) since p E Tu, hence violating calibration. Thus, Tu S To(u) and so (L, 1) indirectly elicit = L indirectly elicits é.
Theorem 7. Let L Rd R" be a polyhedral surrogate that indirectly elicits some target loss (: R + R". Then does not strongly indirectly elicit
Proof. We know from [Finocchiaro et al., 2024] that any polyhedral surrogate has a finite represen- tative set S, i.e., S C RR,, such that S has a finite number of elements and that for any p E An. there exists some u E S, such that p E Iu.. We leverage this fact prove our claim. Assume by contradiction that L strongly indirectly elicits L. Suppose WLOG that S = {ur, th....., " Since Usg[m] A,, it follows that there exists some S' C S, such that relint(11) S U. In particular, S' S and the level-sets of the reports in S" cover relint(71). Since S is finite, there must cxist minimal subset of S, the level sets of whose elements cover relint(11). Assume S' is such a minimal covering subset. First, we claim that for any
S' I. = 7()) n (1} + 0. Assume not. Then 3v E S', such that 7(p) n [1} = 0 for some p E L,,, By strong IE, it holds that y(p) n (1) = 0, T. Thus, if E S', S' can't be minimal. Next, we claim that for any V E S E r. p E T.. By strong IE, follows that Vp E r. {1} C Tpp) = T..p & relint(>)) Thus, o S', S' can't be minimal. Hence, for every E S' - 7(p) = (1). Therefore, relint(m) Ø T, = relint(71) = U.es. T,. However, S" being a subset of finite S is itself finite, and by Lemma 5, Uves r, is finite union of closed sets implying that U, , itself must be closed. On the other hand, relint(y1) ) is not closed by definition and so relint(m)) * UseST Hence, L strongly indirectly eliciting e yields contradiction.
7()) = {1}. Assume not, then Eo E S' {1} C 7P) for some
Lemma 6. Consider any convex, difserentiable L .Rd - RD. Suppose E Rd. Then P, is polytope. If L: Rdd + R2 indirectly elicits any target E: R - Ra, then affdim( w) S m 2.
Proof. Recall by Lemma that r, = {p E An) = 0z}. In other words, r, = A, 0 ker( V [L[()) ). So T, the intersection of a polytope and a subspace, implying that r, itself polytope [Henk al., 2017].
14

---

Next, suppose L indirectly elicits some target é. Then by Lemma 4, it holds that
d rank vank(VV((uT)> > 0. Thus, 1 (ullity(T((uT] n. So, Tu is the intersection of set of affine dimension affdim(T'.) - n
(i.e., An) and subspace of dimension at least (i.e., ker ker(VV((u)))) Thus,
Lemma 7. Suppose & R - R is an elicitable target loss, and that y and R. are finite sets. Suppose further that each r E R non-redundant. Then for any r E R, 7/r a convex polytope, such that affdim(?+))= n
Proof. This can be observed directly from the fact that any finite target is elicitable if and only its cells "r (where, r E R) form a power diagram [Lambert et al., 2008]. Power diagrams are essentially weighted Voronoi diagrams. For more details on power diagram, we refer the reader to [Aurenhammer, 1987].
Lemma 8. Let L: Rd + RR be a convex, differentiable surrogate. Let l R + R". Let u E R Suppose p.P E I'u and that As S R such that 7(p) n 7(p') = S # 0. Then, 7(4) S S, where q: := ptp.
Proof. First note that by convexity of Tu. 9 T. = q E A.. For E R, denote L i), [(2, i... ((n, i)) as the loss vector corresponding to prediction i. Say j E 7(1) I'L S 9 l, vi E R. Now, suppose & S. Let S = t t 7()) n (p')). So, p'Tle S Sp''' Ej and p 4 S p lj. with at least one inequality strict (as if both were equalities, then j E S). So, summing the strict inequality with the other inequality, we get that (v' +p) 4 < (p' + p) Ej
(p'+p) 4 (p'+p) Ej j jēs = 7(0) C.S.
Th < TTL, which contradicts our supposition that j E 7()). Thus,
Lemma 9. Let T, Rdd + R be a convex, difserentiable surrogate. Let 8: R + R Let Rd. such that, (() 0 (p') # 9 for any p.p' E Tw. Let Pm E La h(mm)l S for every e Tww. Then, (Pm) E (p), Vp E l.
Proof. Suppose not. We know that 7 (p) # 0, so SS S R: r(mm) (r(p) 5 5 0. Clearly, S C (Pm) and S C (P), since S + (Pm). Now, pick q ptpm Since Tu is convex, T Now, we know from Lemma that 74) C S = h(a) S ||| <)((m))
In(1 < (pm))
However, since q T T.. this yields contradiction.
Lemma 10.
Let L Rdd R be a convex, differentiable surrogate. Let E: R - R L indirectly elicits l if and only if Yu E Rd, it holds that 71)) nn(')) + 0. for any p.p' E I...
Proof. We first show the = direction. Since L indirectly elicits E, it holds that Yu E R2d Br R. such that In C Tr. Pick any p.p' E Ta. Clearly, p,p' E "r = r E 7()) n 7(1)) (()) rz') A 0, for any p,y' p E r.
We now prove the = direction. Suppose that for any E Rdd it holds that T(p) n 7l/) + 0 for any p.pz E Tu. Let Pm Tu lr(pm)] S h(p),, Vp T.- We know from Lemma 9, that (Pm) C sp)), Vp E T.. This implies that 3r E R : (Pm)
r <(), E I.,
Br E R R:Pp E Tr Vp E Iu = 3r E R: Tu
Lemma 11. Let : Rd + Rn be a convex, differentiable surrogate. Let Cn C Tu be the set of corners T Let E: R RR.. Suppose R. Then, p E irr for every p Cu > Tu -rm
Proof. Recall from Lemma 6 that for any u Rdd, Tn is a polytope. Thus, a finite set C., C T. exists such that C, are the corners of T.. Say 3r E R, such that p E 7r. Vp E C., Pick any & E T.. Clearly, q E conv(C,,) C 7/e 7 is convex by Lemma 7. Thus, q E 7 direction, suppose I'm C 7r. Let C₁ CT. Then E Tr.
= Tu C 7p- For the reverse
Lemma 12. Let L Rd= + RD be a convex, differentiable surrogate. Let Cn T be the set of corners Tf T. for any u E Rdd Let l. R RR.. S8 RR::R:: r(p(p) S for every p E C. then strongly indirectly elicits f.
15

---

Proof. Suppose (p) = S C R. for every E Cu. This implies that p E relint(nres>)) for each p Cn = C2 - relimt((res),)) Since " convex polytope for each S. the set
Oresh is convex and so is the set (ee)))) Hence, conv(C.) C relint(hhes")
ra S
relint(nresth) = p E relint(nreshi)) Vp E T = 7()) S, Ta (pp)),pp.P ET. = strong indirect elicitation is satisfied.
{p)
L
Proposition 1. Let L R R" be convex, differentiable surrogate and let & R R be a target. Let u E IR be a report and suppose C, is the finite set of corners for T. Then the set {r(p))p Cu} suffices to check both indirect elicitation and strong indirect elicitation
Proof. The proof follows by Lemmas and 12.
C Properties of convex, differentiable functions
Lemma 13. Let f Rd I be convex, differentiable function. Then argmin, f()) is convex.
Proof. If argmmn JER= f(u) = 0, the result follows vacuously. Else, suppose f*= min f f'(u) and
that v; y E argmin - f(u). Then for any X E [0, 1], 11xx S x f(x)
f(y)
X. fr + +1 (1-x) 1). --=
A. + x) E J (()), AA E [0.
L
Lemma 14. Let f: Rdd IR be convex finite function RRd. Then argmin uER ['u) is closed. If argmin fu) is bounded, f is compact.
Proof. By [Rockafellar, 1970, Corollary 10.1.1] f continuous. By [Hiriart-Ummuty and Lemaréchal, 1996, Prop 3.2.2] every sublevel-set of f closed.
Lemma 15. Let f _d R be a convex, differentiable function. Then is continuously differen- tiable.
Proof. See Corollary 25.5.1 of [Rockafellar, 1970].
Lemma 16. Let f Fd I. be convex, differentiable function. Suppose also that f is minimizable and that the set sf is bounded. Let Ut == J and ler f" min (u). Then, for 8 > 0, it holds that:
(IEER"BBA fu) inf in = min f
Proof. First, notice that since 4" is bounded, it is compact by Lemma 14. Thus, BB((²)) \ Bs(U)) == (B, ) also compact. Since f differentiable, it is continuous everywhere, and thus attains its infimum over the compact set OB,(U)). This proves that
inf [u] min wEBBs(U))
f(u) > f";
where the final inequality holds as ²B,(U*) nu = 0. We are left to show that
inf
f(u) min f(u). wE0B,((())
B, (c))
Clearly, inf (nfeERABBBau)) f(u) min f(u), for the equality to fail, we would need wer Boarr fu) min f(u). This, in turn, requires that there exist w' Rd (b()))) such that
s(w') < min
s(u).
Pick any w² E 2t and consider the line segment conv(u", u'), connecting u² and u'. There exists some aB,(U)) such that conv u' ). It holds that
f(v) > f(u') > f(u"),
which violates convexity of of since E conv(u", u'), completing the proof.
16

---

Lemma 17. Let f F::" + I be a convex, differentiable function. Suppose also that f is minimizable and that the set U := f is bounded. Let f min f Let {uchEE, be
sequence in Rd Then:
iim (1)) = + (o) - f
Proof. We first show that:
lim d(u,, 11 = 1-00
lim f(u)) = f 100
Since Ut* is bounded, it is compact by Lemma 14. Pick 5 > 0. There exists T3 E N4, such that for every To,
d( < 8.
In partieular, for each 2 T& there exists uf E lt such that
||u - uil || < 8. This implies Bs(lr) S Bs(U)) for every t 2 Ts. Since U is compact, Bs(l*) is also compact.
Now, f is differentiable and therefore continuous everywhere, Since Bz(((") is compact, f is uniformly continuous within (l())). Pick > 0. suffices to show the existence some T N+ such that
(s(w)) - < V. By uniform continuity, there exists 8, > 0 such that
(f) [(w) <e, e, whenever ||u-v/ v/l < and u, E Ba(l").
6, 2 then for any ur with TT.
|/u -ull uill < 8 S dc.
where ut U", implying un, ug E (b(()). Thus, for any 2 To.
ff(4) - f(uā)) 1f(4)) 8r1 <. Otherwise, if & < 6, pick Tg, E N4 such that d(u)21)) < 8. for every t 2 Té,- Then, for each t t2 To, there exists u, U such that
|ue- - uill || < des
u,, u Bz((())
Thus, for all 2 To
(m4) f(1)) 15(4)) 141 <<.
We now prove the reverse direction
lim f(u)= f 50000
lim d(u,, = 0. 450
Assume to the contrary that this implication does not hold. Then, there exists some such that for every T' E N4, there exists t 2 T such that
d(u,, 8.
This implies the existence of subsequence {ut, ijeN, such that
d(u,, ur) 2 6, Vj EJ
For every j E N
f(ue,) 2 inf f(u)= inf Be wEOBs
f(u).
By Lemma 16,
inf wEBBs(u))
f(u) min f(u) 8r wEBB,(U))
Thus, for every E N+.
f(uc,) - min wEOB,(U*)
f(u) fr 0.
This contradicts the assumption that f(u)) f*
oo, completing the proof.
17

---

Lemma 18. Let f1. B + R be convex finite functions such that S1 arg min Er3 f1
and S2 = arg min f2(x) are compact and nonempty. Let g(x) =file =z( + f2(2). Then,
S = arg zeR g(z) is also compact and nonempty.
Proof. By Lemma 14, is closed, so it suffices to show is bounded and nonempty, Fix any I E S and x2 E S2. Let y1 f1( and 1/2 (2 be the minimia achieved by fi and f2. Now, choose any Zg E R² and let y = g(zg). Note that by construction we must have 2 y1 + y2- Therefore, let
= y (y1 + 92) 2
Now, let d1 = diam be the maximum distance between any two points in S1. Then Bed, (d1). the set of points distance 2d, from 21, must be disjoint from S1, so f1 does not achieve its minimum on this set. However, since the set is compact, we can still minimize fi on it. Let oi arg g002, (z1) (x)), and y/ fi (x1) (21.3) y1) and any other point in the epigraph of fi must be entirely contained within the epigraph. In particular, for any I outside the ball of radius 2d1, the line connecting (#1, y1) and (a, f()) must pass through or above (x',9") v") for some x' E Bd2d, (I1). Essentially, this tells us that outside the 2d1 -bll the epigraph of fi lies above the cone of slope 2d,
y1- By convexity, the segment between
- centered X1. Algebraically,
this means that for any x & Bra, (z1). f1(x)= 2
wi-vi
|| xill + y1. In particular, if we let 2d,
max(2d1, - then for any x 4 Br, (21),
f(()) > vi 91
ri
+ y1 2 91 +
2d1
We repeat the same process for z2 and f2, letting d2 diam(S2)
2 = arg min 2dd (22) f2(2)) and U2 f2(2z), and r2 = max(2d2, 82d2 vz- E (x2()
), we have for any
f2(x) > y/2 5
Let B = B (I1) Br, (122). Combining the previous two equations, we have that for any x & B, g (x) = fi(x) + f2(x) > (in + 5) + (y2 + 8) 2 y
Recall that y g(x,) was chosen arbitrarily. In particular, we must have inf g(x) y. Therefore, 9 can achieve its minimum only on B, so we can equivalently define = arg min,eB g(z). Finally, since B is bounded, S must be as well, and since it is closed the argmin of g must be achieved somewhere, so is nonempty.
Theorem 8. Let L Rd + RD. If for each y E [n]. L(-yy : Rd -
R is convex, and arg min I(u)y y is non-empty and compact, then [(p) is non-empty and compact for each p An-
Proof. Pick any p E A,. Then, for each y E [m]. Pv I(-)y is convex. Further, notice that since Py L()), is just L(-)y scaled by positive scalar, it follows that arg min L())g arg L()) and thus, arg min L(-), is non-empty and compact for each E [m]. Applying Lemma 18 inductively, it follows that arg min (p, L(-) is non-empty and compact. Since we picked arbitrarily, it follows that [ppp) is non-empty and compact for each E A.,
D One-Dimensional Surrogate Losses
Definition 7. (Orderable) [Lambert, 2011] A finite property y An = R is orderable, if there is enumeration of R. {r1, ..., ] such that for all < k - 1, we have Try O Tras is a hyperplane intersected with An, We say that the ordered tuple E,, == (r1, Tk) is the enumeration associated with R.
Without loss of generality, we assume for the rest of this section that for any finite orderable property 7. it holds that, 7 O 75+1 hyperplane intersected with An, Vjj E [k - 1]. particular, the enumeration associated with R will always assumed to be E., (1, 2, .... k 1, k).
18

---

Theorem 9. [Finocchiaro et al., 2020] If convex surrogate loss L R - R" indirectly elicits target loss { & - R", then the property ? = prop[é] is orderable.
Definition 8. (Intersection Graph) [Finocchiaro et al., 2020] Given discrete loss e R - RR and associated finite property 7 = prop[e], the intersection graph has vertices RR and edges (r,r') if Jr 0 7er O relini( A.) + O.
Lemma 19. [Finocchiaro et al., 2020] A finite property Y is orderable if and only if its intersection graph is a path, i.e., a connected graph where two nodes have degree 1 and all other nodes have degree? 2.
Lemma 20. Let L U.R- - be convex, differentiable surrogate and suppose R R- R". If L
indirectly elicits l, then there exist disjoint sets 12, 12,12, 1k. C Rd, where for each j E [k I]. E ==² [.. = 7 0 7-41). J. For each j E [K 11, the set P is either singleton {w) } P = {u* closed compact interval [wh. w.
Proof. Since L indirectly elicits E, it follows by Theorem that y is orderable. Thus, for each j E -1-1,, 7/ 07 is hyperplane intersected with A.. Denote T3 := "i 0 7/+1- 1. By the non- redundancy of target reports, it holds for any j E [k [k=1] 1] that affdim(
n affdim(T) - n- and that relint(T;) C relint((..). Fix j E [k- - 1]. Suppose p E relint(T;) - p E relini(A.... By minimizability of (p. I(()), there exists a u² E IR, such that p E P Since I. indirectly elicits f, it follows that T. We first show that w S T Assume to the
follows from Lemma 4 that rank (L.((V)('')) = 1. Further, since p E T us O relint(A,))
affdim(T = 2. Now, we claim that r... contrary. Then, 3p' E I Lul. such that p' & T.. Since I', I' is convex, it follows that conv (p/ .p) C T.. Since is orderable, we know from Lemma 19 that no 3 target cells intersect in relint A... Then, since p lies on the interior of the common boundary between (n- - 2 dimensional) polytopes "6 and Ji+1. there must be sufficiently small O, such that (p) n An is fully contained in relint(7)) in one halfspacc defined by the hyperplane T, and is fully contained in relint(75+3) in the other halfspace defined by Tj. It follows that 3q conv(p', p). such that q relint(7;) or g relint())+1). Suppose WLOG that q E relint( This means that 3q E a (q) = {j}. So, by indirect elicitation, it must hold that T us E "/ and that Tw g % for any # j. However, since T is the intersection of the subspace ker ker(VL((w))) with An. Iw,, must have extremal points the boundaries of A,, This means that Iw cannot terminate at p and must extend beyond p into 7/+--
Thus, 3y E relint( such that Tw. This violates T,, S アÿ and hence violates indirect elicitation. So, [w. T--
For the reverse inclusion, assume to the contrary that Tw C Ty. This means that F. must have an extremal point p E relint(T;). which in turn means that p" E relint(A,.). However, Tws is the intersection of a subspace with A,, so its extremal points must be on the boundary of A.. Thus, Tw TT
Now, define F == fu" E T n- Y/ A 7++1. It follows that u² E T = u² E ((p) since p E 7j n 7/+1- Thus, I, S r(p). However, choosing u² E T(p) arbitrarily, we proved that Tws =7/ 0 77 Thus, r(p) C F.. Therefore, I,- = r(p) which always exists by minimizability of (p, I.()). Further, since T(p) is compact (by assumption). it follows that 1 is either singleton, or a compact interval in R. Similarly, by picking j' [K 1] j' # j. we can establish the existence of (a singleton or compact interval set) P", such that I ra = Yy O 7/ To see that, 1 1 F = 0. Vj. E [k- 1]: + j', assume to the contrary that there exists some u E 1 n P".. Then, r. = 2 0 7-+1 7/ 47 However, 7/ 07++1 # T 01y+1 for any j # j and so the sets 1, and I must be disjoint.
Throughout the rest of this section, we will inherit from Lemma 20, the notation 1 for the set {u² E TR. [T. = 7/ (++1)
Lemma 21. Let L IR + IR" be a convex, differentiable surrogate and suppose & 8: R - I2. Suppose L indirectly elicits f. Let p. E An:::::: :7(2) = {5) and an) = (j + 1}, where j E [k- 1).
Let up E T(p) and Ug E [(4). Then, up < min(()) V (P) < upp or uy < min 15) S
max < Up
Proof. Fix j E [k: - 1). Pick any wt E T5 For p : (p) = 0)4 : 7(1) = [i + 1}. and
Up E [(p), ug E I(g), we will show that exactly one of the following holds: up < w < ui or
19

---

My < u < Up. Now, from the definition of I and from Lemma 3, we know that Fw, = - 0 7/+11 = fr's S An(VL((²) p' = 0}. Since E relin((7;) and relint(7)+11,, it follows that and q are on different sides of the hyperplane fz E R" V (Lu") ) z = 0}. So, it must hold that VL(x)) p < 0 and ( > 0, or that VL(w') > O and V V((w) <.
q > O. Now, notice that ((p, L(-) - VL() p Assume WLOG that (L(u') p < 0 and VL(w') and similarly, (gg. L(-) VL(.) q. Since the function (p, L(.)) is convex and differentiable, it holds from the monotonicity of gradients of convex functions that, (VL(w))T
VL(Up) p, w² w/ Up S 0, since VL(w')T < 0. Clearly, u² * Up and so, u² Up < O. Similarly, we can show that v² - U4 > O. We have thus shown that Uy < u < Up. Since w' was arbitrarily chosen from P. it holds that uy min(P) I max(12) < up
Up) 2 0
(VL(w)) p, u² up) 0
Now, for j E R, denote U = {u E R. u E T(p),7(>) = (i)}-
If instead VL(u)) p > and V q < 0, would follow that up < min(P) S max < Ug by the same argument.
Denote by UJ = {u E R|u Tp)) = (i}}. Let u' U u² E U2 ".....u" u² E Uk. Then by Lemma 21, we know that, w² < min S max( < u² < min((²) I max < uk- < min(Ik-l) I max(I u² max((?) 2 min((?) > v... w²- > min(Tk-2) u+1 > max((<-I) 2 min( > w² This means, that ei- max( min((²). We assume WLOG from hereon, that max(I') < min(Ik-1), Thus, we have shown that min min( is uniform, strict upper bound on U and that max(I) 1) is uniform. striet lower bound on US.
u ... < uk- < min(rk-2) I max((1-2) or, u² > max([") 2 min(!')
u
max(Tk-2)
ther max([²) < mmin((=3)
Theorem 10. Let : R + Rn he a convex, differentiable surrogate and suppose E R. - TR. Under Assumption 1, I. is calibrated with respect to f. Then (I,,) is calibrated with respect to f, for any link vp : R- + R, that satisfies
{i.5 11
if u E T6 for any j E [k -1] 1]
[1}
if u < min(I') if u E (max (Taxx(T--1), min(I))) je2.., if u > mar(1
(u))= E
(2)
{
{1}
Proof. For the entirety of this proof, we define %o 7k+ = 1 = 1 = Let R + R be any
link of the form proposed in the theorem statement. We first show calibration forp E An : 7p) [j) for some j E R. We know from Lemma 21, that max(T < Up < min(T') for any Up E (p)). We have that (u)) # j for any u < min(13-1) and any u > ma)(1"). Whereas, u E 1011 can be linked to either j - 1 or j. and 1 can be linked either j or j + 1. The remaining reports
always link to j.
inf inf (p, I(u) = inf (p, L())
2in 1) #2 (p. L(w)) =min (iiffeeRRuumaa(11111 (p. [u)),, inf, infue (p. I(U))}
-min (p, (mmax(1==))), (p, ((min(1)))) infaeR (p. L(u))
The final equality follows from convexity of the function (p, L(-)). The final strict incquality follows from the fact that max(15-1) Up min( for any up [')... The same argument holds for any other distribution p' : (p/ = [j}. In fact, since j was picked arbitrarily from R, the argument extends to any 9 7(2) = [''}. for any j' E R. So, we have established calibration at all distribution lying in the relative interiors of target cells. We still need to prove calibration for distributions lying on target boundaries.
Again, start by fixing some j E [k-1], 1]. Suppose p E relint(7y(133+1) Then, since 7 orderable, we know from I Lemma 19 that no 3 target cells can intersect in the relative interior of the simplex. Thus, (p)) = [j.j + 1). We have that vi( & [j.j 1 for any u < min( and any u > max max (T)+1). Whereas, p-1 can be linked to either j - 1 or j and u E ufa-1 can be linked to either j or
20

---

j + 1. The remaining reports always link to one of - or
(p, (()) (n
(ww (p, L(u))
iinf (e or =2min(//+1)
I(w))
-min ( (p, (u)), inf, 2 (p. L(n))}
=min (p, (maax(('-)))) (p. [. ((mmn((++))))))>)))))))))))))))) > inf (p. I(u))
The final equality follows from convexity of the function (p, L(-)). The final strict inequality follows by noting that T--10% and Ty++Uuz++ are disjoint from relint(?), (7)++++)))) and hence max (f=-1) and min(7++1) are suboptimal for p E relint(77 75+1). The same argument extends all distributions lying in the relative interiors of target boundaries. Thus, we have established calibration for all distributions, barring distributions on target boundaries that are inside the relative interiors of the boundaries.
Suppose p E A.. such that p lies interior of the target boundary. Such points can lie within the intersection of 2 or more target cells. In case, Nj 7(p) R and calibration follows trivially, since the set E R. (b() 7(p) is empty. Otherwise, suppose, T(p) = S, for some S C R. It must be that discrete reports within S consecutive integers. That suppose j E S and j' E S. Then, either - 1, else, - > then j E S for any j" min(j.J'} < j < max(j, This follows from the fact that y is orderable, and we are assuming the enumeration associated with E, = (1, ..., k 1, k). Thus, suppose that 7(p) = S c R S = {j.j +.J++1. +. J...j t}. where t 2 1. We have that (u) & S for any u < min( and for any u max( Whereas,
target boundary, however, p does not lie in the relative
151 may be linked to either
j - S or E S, and u E 1J+t may be linked to either j +t S or + & S. The remaining surrogate reports always link some discrete report in
inf ((( (D. L(u)) = inf infueR: (p, L(u))
2infueR: or =2min(1>+*) (p, L(w))
-min mnin [u)), inf (p. L(u))}
-min (p. L ((max( (p. L (min( ( )))} > infae (p. L(u))
The final equality follows from convexity of the function (p. L(-)). The final strict inequality follows
by noting that 7-- Ny and & 7s+z O 7/-+11 by construction. Thus, (L, v) is calibrated at The same argument extends to any distribution that lies on some target boundary, but not relative interior.
L
E
Correspondences
We consolidate basic definitions and results about correspondences in this section. Note that different authors can have slightly differing terminology and conventions related to correspondences. We direct the reader Border [2013] and references therein for a more detailed discussion on different conventions. We adopt the conventions, definitions and terminology used in Border [2013].
Definition 9. (Correspondence, graph, image, domain) [Border, 2013] A correspondence from X Y associates each point in X subset sp(x) Y. We write this & X = Y. For correspondence X = Y, let gr pp denote the graph of p, which we define to be
gr & = {(x, E yy p(x))
Let pp X = Y,, and let F C X. The image ((F) of F under yp is defined to be
( U c(x).
DEF
The value xxx) is allowed to be the empty set, but we call {a E X p(x) + 0} the domain of sp denoted dom sp
The terms multifunction, point-to-set mapping, and set-valued function are also used for correspon- dence.
21

---

Definition 10. (Metric upper hemicontinuitt) [Border, 2013] Let X be metric space equipped with the metric dx X X + R. A correspondence yp x Y said to satisfy metric upper hemicontinuity at a point E X ifror every e > 0. 38 0, such that
d(z,z) <8 <0 = ((z) S Be(((x))
Metric upper hemicontinuity is a special case of the more general, topological notion of upper hemicontinuity which requires that the pre-image open neighborhoods of yfx:) be open sets (see [Border, 2013] for formal definition). However, metric upper hemicontinuity at and the topological notion upper hemicontinuity x are equivalent when ((xx) compact (see Proposition 11 of [Border, 2013]). For purposes, this will always be the case. So, we simply work with the simpler, metric based notion of upper hemicontinuity.
Definition 11. (Closed at Closed porrespondence//Bordde 2013] The correspondence & X = Y closed E if whenever In - x, On E ((xx), and yn - y, then y (p(x). correspondence is closed if it is closed at every point of its domain, that is, if its graph is closed.
Lemma 22. [Border, 2013] If the correspondence & = is closed closed set.
Y
X, then sp())
Lemma 23. [Border, 2013] Suppose is compact and @ X = is closed at E X, then y is upper hemiconlinuous at
We say correspondence yp X 3 Y is compact-valued if ppx) is compact for every x E X.
Lemma 24. [Border, 2013] Let C be a compact set and suppose & : X = Y upper hemicontinuous and compact-valued. Then ((K) is compact.
F Sufficiency of Strong Indirect Elicitation
We start by presenting couple of helper results, that we will leverage our main proofs.
Lemma 25. Lebesgue's Number Lemma: (see Thm. IV.5.4 of Hu [1966]) Let (X, d) be a compact metric space. Let A be an arbitrary index set, and U All be an open cover of X. Then, there exists a number dc > O, such that for any X. 252 C. Ua. where E A
Given open cover UI compact set X, constant 8c > 0 that satisfies the condition of Lemma 25 is known as Lebesgue Number for the cover [Hu, 1966]. We state and prove simply corollary of Lemma 25, which will make use of later.
Corollary 1. Let m E Z4, d2 > 0 be a Lebesgue number for some open cover U = Uaealla af compact set X R Then, 22 (X) C cu
Proof. Let E (8)/2(x)). This means, there exist X' and b B8g/2(0mm) such that, v u ie., (uz/ C (u). Now, by Lemma 25, 3a A: Bs, (u) C Ua U. So, E U. Since arbitrarily chosen from (22/2(X), it follows that (22/2 C u
22

---

FA..)
916
Fry
Figure 7: Visual intuition for the proof of sufficiency of strong IE. Let 3.y (1, and R = 21,2,3} (white block with blue border right). Let p A. (black point within triangle left). Tr(p) is the level-set bundle at p (dark purple region left). Here, (p) {2].. Lemma 29 ensures the existence of Ep > The image of [ (p)) (gray region center) under F(.) is fully contained within ?2 (gray region left). By Lemma 27, 36p 0: [(A,) n Bs, (T(p)) (light green region center) is contained within [BB,, (Tr(p))) (gray region center). Thus, every report within the light green region necessarily links to (p) (red block right). So any sequence of reports {ur JEN,, T(An) (light pink region center), for which lim, U4 [pp), must eventually link to (p). Further, Theorem 11 shows how to link nowhere optimal reports without violating calibration. Thus, [pp) is 'protected" in the calibration sense.
Suppose L : Rd + Rd is a convex, differentiable surrogate loss. We assume throughout that for every p E A,, [(p) arg min (p, L(w)) exists and that l(p) is compact. Note that, since the function (p, L(-)) is convex, I(p) is closed by Lemma 14. Thus, it suffices to say [pp) is bounded, though we will usually say compact for clarity.
To prove the sufficiency of strong indirect elicitation, we first establish basic properties about the surrogate level sets (T,/u Rd). To do so, adjust lens slightly, and view r, the image of a correspondence correspondence that maps surrogate reports to the set of distributions they optimize.
point in its domain. In particular,
denote F'.) Rd = A, as the
Lemma 26. The correspondence I RRd A, closed at every I(A,). In fact, T() upper hemicontinuous at every u E (A))
Proof. Suppose u E T(A,) + Tn o G. Let {witee be a sequence in Rdd and let {pihien be sequence in An such that p; E Tu, Vi E and suppose ps + p An and u, + Rd To prove I'() is closed, we need to show p E I, (see Definition 11). Let i E N. Since ps E Fa, V((u)) p; Oa. Now, notice that: [VL(u,)) VI(U)* pll S
V (VL()))) VI(U)T pl
< VL(u))I - [|p--pl VVL(u) VL(u)] [pl]
Observe that lim;- . p (by construction), and lim; lim;-.>.VL(u.)) L( (since uę by construction, and since (.) is continuous). Thus,
lim VL llps pl [V[(u)) ||||=
lim (L, = VL(u)T 0a = p T
We have thus shown that [e, is closed at u. Since the target space, A, compact, the fact that T (-) closed at implies that I' (-) is upper hemicontinuous (by Lemma 23).
23

---

Lemma 27. Letp E An. For every e > O, there exists 8 >> 0, such that: r(A.) n BT(((p) _ ([(B.(Trw))
Proof. Pick any p E A.. Since (()) is upper hemicontinuous at T(p) by Lemma 26, we have that for every e > 0, 36 > O for each u E [(p) such that:
Th C (C( E Bs. (u)
Uw Tw = Bsu (w) C (Ta)
UueT(p) T (w) S UuET(p) Be (TTT)) (T) Be Be(UueT(r) Be (TT())
So, we have shown that UuET(n) Be,, (u) 3 (Tm)).)). It follows by Lemma that:
T(UueT(p) Bo. (w)) (T
(3)
Now, suppose u' E T(A,) n Bs, (u). L'tp' E Tat Then, p/ E Tw C T (o)- So u' E T(p') I[T (w)) Since was picked arbitrarily I(A,) ) Bs, follows that:
r(A,) Bs, (w) S (())
r(Am) ) n UuEr( Bs. (u) C ((T (w)) ()
The final inclusion, i.e., UuEr(P) [(T Bs, (w)) (T(ueT)()) Bs, (w)), holds by the following rationale: Suppose E UuET(p) B(T
Bs., (w)) This means Eu E r(p) E B(TB, (w)) = 3p,
T BB Ba,,(a)) (wt) E (ppo). Now, since Pv TTBe, (w)) (w)) Po E (uET() Ba, u' E {((p). Thus, E ((UwEr(p)) Bou (w)) So, we have shown that:
r(A.) n Uwer(n) Bs. (u) S ((UWeTTO) Bo,
(4)
Observing that the RHS of inclusion (4) and the LHS of inclusion (3) are the same, we combine the inclusions to get that:
T(An) Uuer( Bs, (u) C ((B.((Tr())
(5)
Let us denote Uuer(p) Bs_ (w) by U. Now, notice that l'(p) U. Further, 2/ is a union of open sets and is thus open itself. This means, U is open cover of I(p). Since [(p) is compact, due to Lemma 25, there exists a Lebesgue number & > 0 for U. Set 8 = 62/2. Then, by Corollary 1, (T)))))) C U.
= I(Aw) n Bs((())) CI(An)
= =I(An) n (UuETT) Bs., Bs, (w)
C (T(B,(Tr())
where the final inclusion follows from inclusion (5), thus concluding our proof.
Lemma 28. For any p E An, suppose l'(p) is non-empty, compact set. Then, the set Pr(e))
(n) Tu closed.
Proof. Fix p E An. We know from Lemma 26 that (()) closed at any u E [pp). This implies that for any u E T(p), Tu a closed set. Since the target space A,, is compact, T, must be bounded, and thus I, is compact for each u E T(p). So the restriction of () to [(p), i.e., [ojr() r(p) = A, is upper hemicontinuous and compact-valued, and so by Lemma 24, I Fr(p) is compact since r(p) is compact by assumption. Thus, Trp) closed.
Lemma 29. Let : Rd + RD be a convex, differentiable surrogate. Suppose Assumption holds. Let l: R Th be discrete target loss, with finite property y == prop[ If strongly indirectly elicits e, then the the following holds: For each p E Ani
3 ccp 0: for any E I[B,, (TT()))) holds that 7(9) S <T()), Vg T.
24

---

Proof. Let E An. Define S == Upe Tr. If S is empty, then r(p) = R and 7(')) S 7().. vp E An and then the result follows trivially. Otherwise, notice that 7(g) T()) for any q E Tr(p), since E E T(p) : q T. and then 7p) = (9) by strong indirect elicitation. Thus, (g)) 0, Vq (()) and so S n (T)) = 0. Recall that the target cells, i.e., .r- closed by virtue of being convex polytopes as shown in Lemma 7. So, S is a finite union of closed sets, and is thus closed. In fact S is compact since S An. Also, Fr(p) is closed by Lemma 28. Similarly, I (p)) is compact since Fr(p) C A.. Since S n Tr(p)) 0, and both S and I l'((p) compact and, it holds that d(S,Trra > O. Thus, 3ep 0: Vp' E Beg (I (())) $ S and so:
R are
3ep > 0: Vp' B., (Tr()) 70') S 7())
(6)
Now, suppose v E (T(B,,Tr(e))) T(p') S (p)) due to (6). Now, for any q E Te. it must hold that r(g) = 7(p') ) by strong indirect elicitation. Therefore, 7(q) S 7p), Vi E T.- The result follows since was arbitrarily chosen from TBB (Tr())))
(Tr())). So, there exists y/ E T.,, such that p' E (,,
Lemma 30. Ler : IR + R" be a convex, differentiable surrogate. Suppose Assumption / holds. Then, r(An) is closed.
Proof. We show that for any sequence (ur her, such that u E T(A,)) for each I. E N4. if un + then it holds that u E I. Since u, E T(An), 3p; E An, such that Pt E Pu, for each t N4. can extract subsequence Pt,, such that pt, - P E An and that Me + u. We will show that u E [(p). Consider:
Now, since An is compact,
(T Pt,- - VL(u) T pll - [V ) P', - V PL, (V Pt; - L(uu) T pll 1. [VI((u,,) - L(u)ll + [VL( lpc. -pl
Now, as j - 0o. [VL(u,,) - vl(w)lI - 0 as ut + u (by the continuity of V.(()). Also, lp:r, - pll - 0 by construction. Hence, VL(u,,) ) PTt, 7 VL(u) p. However, since Pt, E I mey"
holds that (((ue, ) 'Pt, 0a = VL(u) T p = 0a = u E (()) = a E r(An), thus concluding our proof.
We are now ready to state and prove our main link construction, which in turn proves the sufficiency of strong IE for calibration under assumptions. Throughout the proof, let dist(a, B) = infoe B ||a bll2. and when the infimum is attained, let grojs(a) == {b E B l|a bllz = dist(a, B)}. for any point and any set B.
Theorem 11. Let I. Rdd - R be convex, differentiable surrogate. Let e: R - R be discrete target loss, with finite property y == prop[[]. Suppose L strongly indirectly elicits E. Under Assumption 1, (L, b) is calibrated with respect for any link vb RRd R, that satisfies the following:
(u) E T()), for any p E To where v E projr(a.)(u)
Proof. First observe that link of form t exists since for any u E Rd, projr (u) is non-empty and well-defined I((A,) is closed by Lemma 30. Now, we show that for any such link v. (L, v)) satisfies calibration with respect to l.
For any p E An, we know from Lemma 29 that there exists some 6p > 0, such that for any E T(B,, (Trg))),i holds that 7(4) S (p), Vq r,, Then, we know from Lemma 27, that there exists 6, such that I'AA.) n Bs, (T()) C E(,,, (Tr())) So,
Vu E T(A..) n Bs, (T(P), S Vo))), E.
Now, suppose there exists link & Rd + R of the form proposed in the theorem statement, such that (L, v) is not calibrated. This means, there exists p E An. such that
inf (p. L(w)) inf (p, L(u)).
Thus, there exists some sequence (we such that (u(e)) & 7(p) but lim (p, I(u))) - infue (p, L()).. It follows from Lemma 17 in Appendix C, that lim dist(u,, [pp) + 0.
25

---

Thus, for some t E N+. it holds that dist u,, I(p)) < 6p/4. Since T(p) is compact, there must be some u² E [p)), such that ||u, - == ||2 < 6//4. However, since v((u,, & 7p), there exists some v projr(a.))(m)) such that |lue - r112 S llue - " "=112 < 6p/4. Further, by the link definition, (14) 7()), and since vb(u) & (p), it holds that (()) 7p), for q E r. However, this
contradicts condition (7) as ||ue - ull2 I I|ue - uel2 + [ 2ll2 < 6p/2. Thus, no such sequence exists and
inf (p. L())) > hnR L(u))
Hence (T,, 1)) is calibrated with respect to f.
G Equivalence of Strong Indirect Elicitation and Calibration under Strong Convexity
Lemma 31. Let L. Rdd Th be convex, differentiable surrogate. Consider the function, Fr. An Rdd + RR where FL u) (p. Mu)). Fr, is continuous.
Proof. Let {(pe, HEN, be sequence in An x Rd, such that lime (p Ut) - (p, u), for some p E An, E Rd. We need to show that lim (pt, L(u))) + (p, L(u)).
((u))) (p. Lu)))) s (pt. L(ue)) (pc. L(w)) ((u)) L(u)) (p, L(u))
< Ipell [[L((e)) - [()]]]] + 1pp pl [|L(w)]
s 1- [|L(u)) - L(will + + 1|pe -ppp pll
Taking the limit as t - 00, [T.))) - T(u)ll + +|[ 1|: pl + 0 since ||p= pll - by construction, and [[[(w,) [(u)ll - 0 as dt 7 u and T.g (.) is continuous for each y E [m]. and thus (ue) + (2),) Vy E [n] = [|L(ue) - L(u) + O. Thus, lime L(ue)) (p, L(u)). and so som (pe, ut) + (r.p. u). whenever lim (Pr, ue) + (p, u). Hence, Fr continuous.
Lemma 32. Let f Rdd TR be a differentiable, strongly convex function. Then arg min f() exists and is singleton.
Lemma 33. [Boyd, 2004] Let f: Rd + R be st-stnongly convex and let Rd + R be My strongly convex. Then f+ g is (1y + (gg)-strongh convex. For any a > 0, the function a f is a ut-- -tr-stooggly convex. Also, f is j--strongly convex for every 0 < J S Hg.
Lemma 34. Let L R& R. be convex, differentiable surrogate. Suppose for each y [n] Ly Fd I is pyy-ttongly convex, where Hy > O. Let Um == minfui Then {p. L(-)) is Am strongly convex, for every E An.
Proof. Let p E An. For any y E [n]. Py Tay is Py By Stronnyyy convex by Lemma 33. Also, (p, L()) = Eyeln Py (.).) yy py- strongly convex by Lemma 33. Notice that, Eye[n Py My I EyEjn)y pm pmm- Thus, (p, L(-)) is pm -n-stlyy convex by Lemma 33.
Lemma 35. Let L Rd + R" be surrogate loss, with strongly convex, differentiable components. Then, P: An 3 Rdd is single-valued and continuous.
Proof. Suppose for each y E [n] Ly Rd + IR is My Hy-Strongly convex, where Hy > 0. Let Um min } Then we know by Lemma 34, that (p. L()) pm -troongyyly convex for every E An. Fix some p E An. Let {pr heN, be a sequence of distributions in A,, such that lim; Pt >>p. p. We know from Lemma 32 that T(p: exists and single-valued for each pt since (pe, L(-) is differentiable and strongly convex. Suppose un E Rd such that u, = I'(p.), for each t tE N.. We need to show that lim Ut + u² where u²" = I(p)) (again, 1'(p) exists and is single-valued).
Suppose V E Rd. We know from Lemma 31 that the function F: A, x Rd, where continuous. Then define m. (r) A,, (q. L(u)) and M, == maxged, (g, L(v)). Both my, M, exist since Fz is continuous, (t) x An and An x (2) are compact. Now, pick any
(.)()) L(-))
26

---

w E IR" ||0|| = 1. Let > max 11 2:(M,-mu)), Let in == t w and U2 == u B- w. Notice,
Mm
1-1 + 222. Next, for any E An. we have that:
my S (q, ((vi))
8 -
1
1
3 - 11 1
8
(g, L(v)) + (1, L(v2))
B
2 Mm
B
B
111 w2
8 (g, L(v)) + (1, L(v2))
1
1
(3 -11 1)
B
B
2
amm
So we have established that,
8 --1
1 B (g. L(v) + (q. L(v2) pm (B
my S
(8)
The first inequality holds due the definition of m. The second inequality follows by Jm -Stong convexity and the final equality follows from the definition of U2. Now, we claim that, {q. L(22)) >
(q, L(v)). Assume to the contrary that (q. L(22)) S (q, L(v)). Since, M, 2 (q, L())), we get by (8) (B 1) - m. - M, S - Me (8 -
that, m, S M, - 1 pm
3 1+ mm))
M4m
which violates the condition for choosing 3 >> max (1, 1 2(M,--=)) Thus, (q. [(u)) > (g. L(w))
Pm
for any u ||0 =|| > max (1, 2-(M.-m-)) } and any q E An. since 1/2 = v + B for Am
arbitrary w Rd : ||=||| = 1 and 3 > max 2.(M, mmm] } was chosen arbitrarily, followed Am by which g E A,, was also arbitrarily picked. Thus, for any q An. ((g) must be such that [[))] S max(1, + 2-(M.-mo)) since (q, I(T(a))) S (q, L(v))- Thus, r(An) is uniformly T(P))EE,, must be bounded as
pm bounded in a ball around And so, the sequence {ue]ER, well. Thus, there exists u' I2d and a subsequence (u,, IeN, such that lim Me, + u'. By definition, (pr,, L(ue,,) )) & (Pt,. L(u)) for every u E Rd. Thus, by continuity of FL, we have that (p, L(x') < (p, L(u)), Vu E Rd. Since (p. L(-)) admits a unique minimizer, it follows that u' = u = T(p). Thus, every convergent subsequence of {ur heN, must converge to the same limit u², and as {ue HeN, is bounded, lim U = u [pp).
Thus, we have shown that for any p E A, and any sequence of distributions {peLIN,, such that lim;-ro Pt - it follows that (pt)) + [pp). Thus, I is continuous.
Li
RD be surrogate loss with strongly convex, disferentiable components. Let 8: R- > TR. If indirectly elicits f, but does not strongly indirectly elicit f, there exists some report u. E Rd, such that 7((m) (()), for some Pm, E Tw.
Lemma 36. Let L: Rd >RR"
Proof. We claim that 3p','' E Fu. such that hyd) A (n(4)). Assume to the contrary that for
every p.g E Tu. [7()] 1z(2). So, we have that Eu E Rdd such that r(p") * 7(g"), but hx(p") ) = hyg")] ). Sine I. indirectly elicits f, we have by Lemma 10 that 7(")) ) 0 (7((")) & 0. So
ES C R
# and S = T(")) n r(g),, while 5 C xrp") and C rgg)). In particular, this
means |S| < hn(=). Now, we know by Lemma 8 that p'tg is such that >( (( C S. This means htp" +4" ) < [S] < hr(") = hyp" +o"
2
2 ) < 7(p) which contradicts our assumption since p'tg" rr by convexity of Thus, 3p',d' E E... such that 17(2)) * Ix(g)))-
2
Let Pm E <r. (p())) ) (p()),, vp E T.. We know by Lemma 9 that 7(m)) E 7P),, Vp E T.. In fact, 3p E I. hp() # h(pm)) = hr(m)) < htp) and so 7pm) Cp()).
Theorem 12. Let L Rd + R." be a surrogate loss, with strongly conver, differentiable components. Let e: R > RR. I. such that (I, v) satisfies calibration with respect to E.
L. does not strongly indirectly elicit e, then there is no link function 1) R.d - R.
Proof. First, suppose L does not indirectly elicit Then straight away, calibration fails since calibration implies indirect elicitation by Theorem 6. Now, suppose L indirectly elicits f, but does not strongly indirectly elicit We know from Lemma 36, that for some u E R2d 7(pm) C 7P)) where Pm. P& E F Assume WLOG that (pm)) {1, ..., t) and that 7(p) (1, ..., t,.., +
27

---

where j 2 1. In particular, p lies on the boundary of the cell 74+1. which is convex polytope. Thus, can pick sequence (p, Jpeee such that 7(p,) {t 11+1), E N_. and lim; Pt - p. Define = T(p;), for every E N+. Then, we have by Lemma 35 that since each of the components of are differentiable and strongly convex, holds that continuous and hence +im 14- u. To ensure calibration at Pm- it is necessary (b)) E 7(mm), since u = T (pmm) and 7(pm) S (p), vp E Tu. Also, to ensure calibration at p; it is necessary that v(v)) = t + 1, since ((1) (f + }} for every i E N4. However, despite this, we show calibration fails:
inf (0)
(pmi L(u)) S
inf (pm: L(v))
(0R+:0(0)=111
inf VERAiVE(Miteo
(pm: L(v))
lim (pm, L(vi))
(p, [p.) inf (p. L(v))
vER"
Hence, we have shown that inf inf (pm: L(v)) inf (p, L(v)), thus violating cali- bration Pm-
H Constructing 1d surrogates for orderable properties
In this section, we provide an explicit construction of a consistent, convex, differentiable surrogate with domain dimension for given orderable target loss. Formally, given orderable target, :: R + R","" we prove constructively the existence of a convex, differentiable surrogate L R - RR" that is consistent with respect to L.
Our construction hinges on a subroutine which we will call LinIntGrad(X)) Given vector X = for some integer & 2 2, LinIntGrad constructs a function f IR R that is convex. differentiable and whose gradients match X at inputs 21, 2, .., k 1}, i... f'(i) = -X Vi E [K 1].
See Subroutine for the detailed construction.
Subroutine LinIntGrad(X)
1: Input: [[]],..,, X [ 1] (with 2 2)
2: Goal: Define a gradient map g IR - R and f(x) = J g(t) dt
3: (A) Define on k-) by linear interpolation
4: for j = 1,2,.... k 2 do
5:
For x E (i.j+1) [k-1}; 1}. set
g(x) t- X + (x- () -(1)-
6: (B) Left extrapolation (-o0,
7: For x S 1, set
g(x) + X[1] + (x - 1)
8: (C) Right extrapolation on 11)
9: For x 2 1, set
g(z) Xik 1] + (x (k- 1))
10: (D) Define !
11: f()
s(t) dt
return
Lemma 37. Given some X RR- where k is integer. Following the notation of Subroutine 1, let g be the gradient-map constructed and let f = LinIntGrad(X)), Then:
(i) g continuous and nondecreasing on R.
(ii) f is convex and Cº on R, with (x) g(x) for all
28

---

(iii) f((1= X for each i E fl....,k 1}.
(iv) Minimizer location:
In Case 1 (X(1) S X - 11,, one has arg mign I S [1 - 11. 1f = 0 on
otherwise g crosses 0 inside [1. k - 1] and the minimizer lies there (unique the crossing is strict).
{1....,k kk -1 then arg min [1, 11;
In Case 2, when X[1] > 0, arg min f {1 [[1]
In Case 3, when X 1] < O, arg min f { X 1]}.
(v) arg min J is nonempty and compact.
Proof. (i) Continuity and monotonicity of g. First, consider the behavior of g on the interval (1, k - 1)
see (A) in Subroutine 1. On each sub-interval, i.e., each element of the set {(j.j + +1] {k-
1H1i E [k: - 21}. is either affine with nonnegative slope or constant. Thus, 9 is continuous on
(j.j + 1), and nondecreasing
(j.j + 1] \ { - 1). vij E [k 2]. Let j {2, 3, .... k 2).
We have that s(i-) == lim xij - 1 + (c - (j - [x - x 1]) = X while
g(i+)= := lim [ + (x - -X
= [i]. Thus,
X = g0).
Hence g is continuous on (1.j - 1). We already know g is non-decreasing on each subinterval.
Notice also that, g()) = xx < X(j+ 1|= g + 1). Hence, g is non-decreasing and continuous
=gj
on (1.j -1.--1).. 1).
We now analyze continuity a = 1; see (B) in Subroutine I: for x S 1, we set g(x) = ((-)+ For æ E (1,2), 2). we have g(x) = [[]] + (z (x - -[]] Clearly, lim,-11 -00-->>11>>>>>>> = X[1] ( Thus g is continuous
1.
similar check at x = k - 1; see (C) in Subroutine 1: For x E (k - 2, k - 1)) X|k 2] (z (k: 2)) (x[k -1 1
2)). So, lim g(z) X 1]. Whereas, for 2 1. (k: 1)). So, lim=-((-1)-9(1)) x 1]. Hence g continuous at 1
g(x) = X -1++
and k- 1, which means g is continuous [1, - 1]. On (-o0, 1). well as (k- - 1, oo), g is affine
with non-negative slope. Thus, is continuous and non-decreasing on R.
(ii) Convexity and differentiability of f. Since f(x) = J g(t) dt, f is C²(R) with I = everywhere. So f' is monotone (since g is nondecreasing), and hence f is convex.
(iil) Gradients match X in [k- - 1]. For each j E fl....,,k kt - 1}. the interpolation g(z) = (x j) gives g(j) = X(s). Hence f'()) = g(t) = X(s).
X + []
(iv) Minimizer location. Recall that for differentiable convex f. any minimizer xt satisfies f'(x*) = O. and conversely if f' changes sign from negative to positive at x*, then x* the unique minimizer.
Case 1 [X[1] $ 0 < Xík: - 1)): If [ < O, then g(z) = X[1] < 0, Vx < 1. Whereas, if X[1] = O. then 9(x) = - < 0, Vr < 1. Either way, g(z) * 0 for any z < 0. Similarly, if X[k 1] > 0. then
g(x) = X[k - 1| > 0, Vr 2 - 1. Whereas, if X[k - 1] = 0, g(x) = x (k 1) > 0, Vx > k 1.
Either way, 91x) # 0 for any
k- 1. Thus, 9 # 0 on (-00, (1, 00).
On -1, 1). g is continuous and nondecreasing with =[] < and g( - 1) = X hence any zero of lies in 1 1]. If X = 0 on (1...., 1), we have
0 on 11, 1]. If
not, 9 must cross 0 somewhere in [1, k - 1] due to continuity. Thus, arg min f S [1, k - and arg min f 3 0. So arg min f is non-empty and bounded. Since f is convex, arg min f is closed, and hence compact.
Case 2 [X[ > 0): First notice that in this case, since X > 0, 9(1) O and since g is nondecreasing it follows that g(z) > for every x 2 1. So any zero g attains must be in (-00, 1).
For x < 1, g(z) = [[1] + (z - 1) = 0 + x = - X[1] < 1. Since g is strictly increasing on
(-oo, 1), it crosses exactly once at - X(1). Thus, arg min f = (1 - [[]) which is non-empty and compact.
Case (X(k- 1] < 0): First notice that in this case, since X 1] < 0, g( 11 0 and since
g is nondecreasing it follows that g(x) < 0 for every x < k: - 1. So any zero attains must be in
1,) For x > k- 1, g(x) = X [[[--]]- 1]] (x- (k- - 1)) = 0 + x = k k 1 X l 1] > 1-1.
Since is strictly increasing on (I: - 1, oc), it crosses 0 exactly once at
- X - 1]. Thus,
arg min f (k- - 1 X [k- - 1}} which is non-empty and compact.
29

---

(v) min f is non-empry and compact. Follows directly from part (iv).
Construction 2 SURROCATE CONSTRUCTION
1: Inputs: Vl V!...., V R (rows of matrix V)
2: Output: Consistent, convex and differentiable surrogate loss L R"
3: for all j [ni] do
4: L(-), +- -LiIInGGaa((V)))
5: Define I T(u) + [L(u), (u.),...., [(u)n)
6: return
Theorem 13, Given an orderable target & - R", there exists a convex, differentiable surrogate
L IR - Rn safisfying Assumption I, which is calibrated with respect to f. In parficular, Construction
2 yields such surrogate loss I..
Proof. Since y prop is orderable, there exists orderable enumeration of R, i.e., E, (Ti, T2,,,, Th. (see Definition 7). We know from Theorem 11 of Finocchiaro et al. [2020] that there exists set (V1, U2,,.., 1k-1) C IR" such that:
The set satisfies coordinate-wise monotonicity. That is, E [A 18-22 22,, E [n]] holds that,
Viyy I Uit.y*
2. The set of vectors are normal to target boundaries, i.e., Vp Yr, O Trai (v, uz) 0.
Let us denote by V E 1axk-1 the matrix with column vectors U2 ... Uk-1 in that or- der. Let V E [n] denote the 7th row of V. These row-vectors are as inputs the surrogate construction described in Construction 2. We now show that the output of L SURROGATE CONSTRUCTION(V!. V??...,, V*) is convex, differentiable, satisfies Assumption and is consistent w.r.t. E.
Each component I(-),, [ni] defined in Construction 2, is obtained via Subroutine 1. Thus, for each j E [n). I(.), is convex, differentiable and satisfies Assumption by Lemma 37. We show that indirectly elicits l and the result then follows by Theorem 1.
Assume does not indirectly elicit L. This means, there exists some u R, such that I., & Tr, Vr R. In particular, this means that the level-set I, crosses from target cell's relative interior into another target cell's relative interior. By convexity of u. there exists some j E [k 1] and some p Yr Try-- such that p Tw. By construction,
VL(j) ez. Clearly, u # j as L( * vy- Assume WLOG that u < j. This means VL(u) [(j) 8, where & 0, Vi [n] and o,- > 0
for some i" e [n]. So. (p, VL(w)) = (p. VL(j) 6) - (p. 8) < by the condition on d. Thus, p & l. yielding contradiction. Hence L must indirectly elicit L.
30

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: [Yes]
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: [Yes]
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
31

---

Justification: [Yes]
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: There are no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
32

---

Answer:
[NA]
Justification:
There is no data or code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurlPS code and data submission guidelines (https: /ttsss////pp////ee cc/ des CoodeSuomei ssionni asionooll iiyy) for more details.
publ public/ / guides
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / //nips. cc/ cttpsscccppplliiec pwppppplc////o wwwpc//gues/////eeeee /Codee////oeese CodeooeeSSaa CCodSSummll Submi pommissa ssiisssinnn cessonnPoicyyy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
We use no data.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: We have no data.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
33

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: We just used our brains.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /et:://neeuse /neurips....p// ct/ppubbccc/.tccccccccelelllllll
Answer: [Yes]
Justification: [Yes]
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: How could theorists possibly affect society let's be honest.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
34

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We don't 't have data models. We theorists.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: [Yes]
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of the package should be provided. For popular datasets, papers seww swittwiii wwooeedee com/ dataset has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
35

---

Answer:
[NA]
Justification:
We are tragically asset-less.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/codd/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
We didn't do any experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
We didn't do human trials.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
36

---

Justification:
We only used them for editing.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https: : / http///ii..c//oooeeeeeeeeeeeeeee confeeeeeeeessss / 2025/
LLM) for what should or should not be described.
37


Reviews:
[{"review_id": "aayDG2MXo5", "reviewer": "Reviewer_u7xK", "summary": "The paper introduces a new approach for proving consistency of differentiable surrogate losses. Their approach studies how the indirect elicitation can be used to prove calibration and thus statistical consistency. Within the paper they highlight examples of when indirect elicitation and calibration simultaneously hold and when they do not simultaneously hold. They then prove that calibration holds for 1-dimensional continuous and differentiable surrogates that indirectly elicit the target loss. To handle higher dimensional surrogates, they introduce the strong indirect elicitation condition to prove the same calibration result. Finally, they show for strongly convex surrogates that strong indirect elicitation is equivalent to calibration. The remainder of the paper highlights how their approach simplifies existing proofs proving calibration for the statistical consistency of surrogates.", "questions": "1. Can more detailed be provided why Example 6 fixes the issues of Example 1? In particular, the last argument in Example 6 seems to hold for Example 1 since $L$ is strictly convex for Example 1 as well. \n2. Are there some simple examples or intuition for when $\\gamma$ is order able?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "#Strengths\n1. The paper introduces a useful and simpler technique for proving the statistical consistency of surrogate losses.\n2. The paper provides useful examples highlighting how using indirect elicitation simplifies complicated calibration proofs. \n\n#Weaknesses\n1. From a broader perspective, it's hard to understand if there's any drawbacks of only focusing on surrogate losses which it is easy to prove indirect elicitation. Or in the opposite perspective, there's limited intuition on what settings naturally lead to creating a surrogate with indirect elicitation. As a result it's hard to measure how general this approach is in developing new surrogate losses.\n2. The exposition and notation could be improved in some sections of the paper. For example for notation, $\\gamma_{\\gamma(p)}$ in example 6 is some what confusing based on its definition in Definition 1. Similarly, the authors use $p = (1/2, 0, 1/2)$ even though $p$ is used more often as a generic input for $\\gamma$ and $\\Gamma$.  Exposition-wise, it was hard to follow the intuition for why Example 1 shows a surrogate loss can satisfy IE but not calibration especially when compared to Example 6. In particular, it was hard to see why the last argument in Example 6 doesn't hold for Example 1.", "was_revised": true, "final_justification": "The paper seems to provide novel theoretical contribution towards understanding the consistency of surrogates losses. My issues with the paper mainly arise from the exposition as it is somewhat hard to follow and feels written primarily for researchers who have extensive background knowledge in the area. The authors' rebuttals to my and other reviewers' questions were helpful, however, it is hard for me to increase the score since it is less in my area of expertise and thus am more willing to defer to the other reviewers.", "rebuttal": "Thank you for your time and helpful feedback. We will improve and clarify the technical notation in the paper. We address specific concerns and questions below. \n\n$$\\textbf{‘‘...  As a result it's hard to measure how general this approach is in developing new surrogate losses.\"}$$\nWhile our paper's primary focus is not on designing novel surrogates, we have taken important first steps towards discovering novel consistent surrogates satisfying convexity and differentiability. Specifically: \n\n1) The conditions of IE and strong IE are simpler to verify than calibration, offering practical tools to more efficiently evaluate and prototype candidate surrogates. See Theorem 4 and Example 5.\n\n2) Our results mirror prior work on polyhedral surrogates ([1]), where an analogous IE-calibration equivalence led to rapid progress in designing novel surrogates in the polyhedral setting ([2]–[5]). Notably, this equivalence enabled the resolution of open problems such as the construction of consistent polyhedral surrogates for top-k classification [3], despite earlier negative conjectures [6]. The fact that such conjectures were overturned using simpler IE-based reasoning underscores how opaque and non-constructive calibration alone can be. \n\n$$\\textbf{‘‘... the last argument in Example 6 seems to hold for Example 1 since $L$\n is strictly convex for Example 1 as well.\"}$$\nThe two examples use different links. We will make this more obvious. The inequality from Example 6 that you reference makes implicit use of the link definition $\\textit{before}$ invoking strict-convexity. \n\nTo elaborate: the set of distributions where abstaining is target-optimal is $\\gamma_{\\bot} = \\\\{p \\in \\Delta_2 : \\max{p_1, p_2} \\leq 0.75\\\\}$. Consider $q = [0.5, 0.5]$, so $q \\in \\gamma_{\\bot}$. Calibration holds for example 6 but fails for example 1 at $q$. \n\n$\\textbf{Example 6}$: $\\psi_{smooth}(u) = \\bot$ iff $u \\in [-0.5,0.5]$. So, $\\\\{u: \\psi_{smooth}(u) \\notin \\bot\\\\} = \\\\{u: u \\notin [-0.5,0.5]\\\\}$. Recall also that $\\Gamma_{smooth}(q) = \\\\{0\\\\}$. Thus, $inf_{u: \\psi_{smooth}(u) \\notin \\bot} \\langle q,  L_{smooth}(u) \\rangle = inf_{u: u \\notin [-0.5, 0.5] } \\langle q, L_{smooth}(u) \\rangle >  inf_{u: u \\in [-\\epsilon, \\epsilon] } \\langle q, L_{smooth}(u) \\rangle = \\langle q, L_{smooth}(0) \\rangle$, where the inequality holds for a small enough $\\epsilon$, say $\\epsilon = 0.1$ by strict-convexity (the function value grows away from the minimum). \n\n$\\textbf{Example 1}$: Here, we $\\textit{only}$ link $0$ to $\\bot$, i.e., $\\psi_{cusp}(u) = \\bot \\iff u = 0$. Hence $inf_{u: \\psi_{cusp}(u) \\notin \\bot} \\langle q, L_{cusp}(u) \\rangle = inf_{u: u \\notin \\\\{0\\\\}} \\langle q, L_{cusp}(u) \\rangle$ and there is no $\\epsilon > 0$ satisfying, $inf_{u: u \\notin \\\\{0\\\\}} \\langle q, L_{cusp}(u) \\rangle >  inf_{u: u \\in [-\\epsilon, \\epsilon] } \\langle q, L_{cusp}(u) \\rangle$. Here too, $\\Gamma_{cusp}(q) = \\\\{0\\\\}$ and hence any non-zero sequence converging to $0$ minimizes $\\langle q, L_{cusp}(\\cdot) \\rangle$ despite that sequence never linking to $\\bot$, which violates calibration. \n\n$$\\textbf{“Are there some simple examples or intuition for when $\\gamma$ is orderable?\"}$$\nYes, see our Example 5 (ordinal regression loss), or Example 9 in [7] ($\\epsilon$-insensitive loss for robust classification). Other orderable properties include the median and the ratio-of-expectations [9]. Intuitively, a target loss is orderable if it is possible to draw a line segment through the simplex such that it intersects $\\textit{every}$ target-cell. See [8, Figures 1 and 2] for a visual comparison between orderable and non-orderable properties.\n\n$\\textbf{References}$\n \n[1] J. J. Finocchiaro, R. Frongillo, B. Waggoner. \"An Embedding Framework for Consistent Polyhedral Surrogates\". NeurIPS 2019\n\n[2] Y. Wang and C. Scott. \"Weston-watkins hinge loss and ordered partitions\". NeurIPS 2020\n\n[3] J. J. Finocchiaro, R. Frongillo, E. Goodwill, and A. Thilagar. \"Consistent polyhedral surrogates\nfor top-k classification and variants.\" ICML 2022\n\n[4] J. J. Finocchiaro, R. Frongillo, and E. B. Nueve. \"The structured abstain problem and the lovász hinge\". COLT 2022\n\n[5] E. Nueve, D. Kimpara, B. Waggoner, and J. Finocchiaro. \"Trading off consistency and dimensionality\nof convex surrogates for multiclass classification\". NeurIPS 2024\n\n[6] F. Yang and S. Koyejo. \"On the consistency of top-k\nsurrogate losses.\" ICML 2020\n\n[7] H. G. Ramaswamy and S. Agarwal. \"Convex calibration dimension for multiclass loss matrices.\" JMLR 2016\n\n[8] J. Finocchiaro, R. Frongillo, and B. Waggoner. \"Embedding dimension of polyhedral losses\" COLT 2020\n\n[9] N. S. Lambert, D. M. Pennock, and Y. Shoham. “Eliciting properties of probability distributions.” In Proceedings of the 9th ACM Conference on Electronic Commerce, 2008"}, {"review_id": "mYoObdnAeU", "reviewer": "Reviewer_fLKV", "summary": "This work establishes general calibration conditions on convex differentiable surrogate losses for domains with discrete targets. Previous work had shown that calibration and Indirect Elicitation (IE) are equivalent for polyhedral surrogates. This work extends the results and introduces the notion of strong IE, which implies calibration for differentiable functions. Strong IE is also shown to be a necessary and sufficient condition for calibration for the case of strongly convex differentiable functions. The paper also shows that for 1-d convex losses, IE and calibration are equivalent. But this equivalence breaks in higher dimensions, requiring the use of strong IE for calibration. This is made clear with a number of counter examples in the paper.\n\nThe theoretical results in the paper makes it possible to more easily analyse and prove calibration for previously studied surrogate losses. Examples 3 and 4 in the paper are proven using the results of Theorems 2 and 3, resulting in significantly shortened proof of calibration. The paper also introduces a Huber-like surrogate for ordinal regression (Example 5), which is shown to be calibrated as a 1-dimensional convex and differentiable function. There are no empirical studies present in the paper.", "questions": "- Is it possible to design higher dimensional surrogates using the insights of Theorem 3? Are there any examples that could be added to the paper?\n- Line 106: IIUC this looks incorrect. \"For any r\" instead of \"For any u\".", "limitations": "The paper has sufficiently discussed its limitations and potentials for future work in section 5.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Quality, Clarity: The paper is overall well written, but the specific terminology and overloaded notation can be cumbersome to deal with. The work is motivated mostly in theory, without much attention to empirical implications. The paper can greatly benefit from examples of misbehaved training due to lack of calibration for the chosen surrogate loss.\n\nSignificance, Originality: The study of calibration for non-polyhedral losses is new to this work (to the best of my knowledge). Theorems 2, 3 and 4 are novel and can be used (as demonstrated in 4.1) to easily prove calibration for a large class of surrogate losses. However, IIUC, there is only one novel Huber-like surrogate loss presented in this work (Example 5), the design of which is rooted in Theorem 4. The paper can greatly benefit from other constructions that might be possible with the insights and theorems presented in the work.", "was_revised": true, "final_justification": "The rebuttal answered some of the concerns and questions raised in my review. I'm updating the overall score based on the updated version with expanded discussions and added citations.", "rebuttal": "Thank you for your time and helpful feedback. We will improve and clarify the technical notation in the paper. We address specific concerns and questions below. \n\n$$\\textbf{“The paper can greatly benefit from examples of misbehaved training due to lack of calibration for the chosen surrogate loss.\"}$$\nStatistical consistency (and hence calibration) is a fundamental requirement for ensuring compatibility between a surrogate and target loss. This long-standing literature goes back to at least Bartlett et al. (2006) [1] and has since been an active area of research. \n\n$$\\textbf{“However, IIUC, there is only one novel Huber-like surrogate loss presented in this work (Example 5), the design of which is rooted in Theorem 4. The paper can greatly benefit from other constructions that might be possible with the insights and theorems presented in the work\"}$$\nWe also provide a general-purpose construction for designing convex, differentiable surrogates for orderable targets. Our results can enable new convex, differentiable surrogate designs—just as the IE-calibration equivalence in [3] led to progress on consistent polyhedral surrogates [4–7].\n\n$$\\textbf{“Is it possible to design higher dimensional surrogates using the insights of Theorem 3? Are there any examples that could be added to the paper?\"}$$\nHigh-dimensional surrogates—e.g., $(n-1)$-dimensional consistent surrogates for $n$ outcomes—are already known (see Lemma 11, p.19 of [2]). Low-dimensionality is desirable as it can yield significant computational savings during optimization.\n\n$$\\textbf{References}$$\n[1] P. L. Bartlett, M. I. Jordan, and J. D. McAuliffe. \"Convexity, classification, and risk bounds\". Journal of the American Statistical Association, 2006\n\n[2] H. G. Ramaswamy and S. Agarwal. \"Convex calibration dimension for multiclass loss matrices.\" JMLR 2016\n\n[3] J. J. Finocchiaro, R. Frongillo, B. Waggoner. \"An Embedding Framework for Consistent Polyhedral Surrogates\". NeurIPS 2019\n\n[4] Y. Wang and C. Scott. \"Weston-watkins hinge loss and ordered partitions\". NeurIPS 2020\n\n[5] J. J. Finocchiaro, R. Frongillo, E. Goodwill, and A. Thilagar. \"Consistent polyhedral surrogates\nfor top-k classification and variants.\" ICML 2022\n\n[6] J. J. Finocchiaro, R. Frongillo, and E. B. Nueve. \"The structured abstain problem and the lovász hinge\". COLT 2022\n\n[7] E. Nueve, D. Kimpara, B. Waggoner, and J. Finocchiaro. \"Trading off consistency and dimensionality\nof convex surrogates for multiclass classification\". NeurIPS 2024"}, {"review_id": "4Mhw4i5fYo", "reviewer": "Reviewer_zx7Y", "summary": "The paper tackles the long-standing challenge of certifying when a convex, differentiable surrogate loss is statistically consistent with a desired discrete target loss.  Building on the simpler condition of indirect elicitation (IE), the authors show that for any one-dimensional convex differentiable surrogate, IE is equivalent to the standard calibration criterion that underpins consistency.  They then construct a concrete two-dimensional counter-example demonstrating that this equivalence breaks in higher dimensions, motivating a new, equally easy-to-check notion called strong IE.  Strong IE is proved to imply calibration for all convex differentiable surrogates and to be both necessary and sufficient when the surrogate is also strongly convex.", "questions": "* All your guarantees assume the learner reaches an *exact* minimiser of the surrogate risk. In practice we obtain only $\\epsilon$-optimal solutions. How does this gap affect the IE / strong-IE ⇒ calibration implications?\n  \n* Can the new surrogates certified by strong IE be trained effectively, and do they improve accuracy or calibration error on real data versus standard baselines?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\nThis paper\n\n* Presents rigorous, fully detailed proofs that are internally consistent and build on well-established convex-analysis tools.\n  \n* Moves the theory of consistent surrogates beyond polyhedral losses, which dominate prior work, to the far larger class of smooth losses common in deep learning.\n  \n* Strong IE itself is a novel concept that generalises earlier “flat-cell” ideas from the polyhedral setting but is tailored to smooth objectives.\n  \n\n## Weaknesses\n\n* Empirical validation is minimal: there is no experiment showing that strong-IE-certified surrogates actually improve learning outcomes compared to uncertified baselines.\n  \n* Contributions are purely theoretical; no new algorithmic techniques or optimisation heuristics are proposed, limiting novelty on the applied side.\n  \n* Dense notation and frequent switching between set-valued and point-wise views ($\\Gamma(p)$, $\\Gamma_u$, $\\gamma_r$) can overwhelm readers;\n  \n\nI carefully bid for papers that match my areas of expertise, but this paper lies outside my core research interests. Although I work on the theory of machine learning, I found the paper difficult to follow. If the authors were writing for a journal without page constraints, they could devote more space to intuitive explanations, clearer notation, and motivating examples. A thorough rewrite with a simpler narrative flow would greatly improve accessibility for readers who are not already experts in this field.", "was_revised": true, "final_justification": "This paper gives a clear, rigorous criterion—strong IE—for when smooth convex surrogates are consistent with a discrete target loss. In 1D it shows IE and calibration coincide; a 2D counterexample shows where this breaks, motivating strong IE, which implies calibration for all convex differentiable surrogates and is necessary and sufficient under strong convexity. The results extend beyond the usual polyhedral setting and are backed by careful proofs; there’s also a constructive path for 1D orderable targets (used in an ordinal-regression example).\n\nThe downsides are practical: no experiments, no optimization heuristics, and dense notation that hurts accessibility. The rebuttal helps—consistency already covers ε-optimal solutions, and the authors will streamline the exposition—but there is still no empirical check or rate-style bound. Accordingly, I cannot fully endorse acceptance, but I recognize the paper’s merits and maintain a borderline accept (4).", "rebuttal": "Thank you for your time and helpful feedback. We will improve and clarify the technical notation in the paper. We address specific concerns and questions below.\n\n$$\\textbf{“Empirical validation is minimal: there is no experiment showing that strong-IE-certified surrogates actually improve learning outcomes compared to uncertified baselines.”}$$\nOur results show that strong IE guarantees calibration for convex, differentiable surrogates. In this setting, certifying strong IE certifies calibration—and thus consistency. Statistical consistency is a fundamental requirement for surrogate-target alignment going back to at least Bartlett et al. (2006) [1].\n\n$$\\textbf{“Contributions are purely theoretical; no new algorithmic techniques or optimisation heuristics are proposed, limiting novelty on the applied side.”}$$\nOur focus is indeed on theory, which is badly needed in the design of surrogate losses. That said, we are motivated by a practical challenge: calibration is often hard to verify. We provide simpler, verifiable conditions—like strong IE—that imply calibration for convex, differentiable surrogates. Prior IE-calibration equivalence for polyhedral surrogates [2] spurred the design of new consistent losses [3–6]; we expect similar impact here. As an initial application of our theory, Theorem 4 provides a constructive method for building consistent 1D differentiable surrogates for orderable targets, which we use in Example 5 to design a novel surrogate for ordinal regression.\n\n$$\\textbf{“All your guarantees assume the learner reaches an exact minimiser of the surrogate risk. In practice we obtain only $\\epsilon$-optimal solutions. How does this gap affect the IE / strong-IE ⇒ calibration implications?”}$$\nWhile IE and strong IE allow us to $\\textit{reason}$ only about exact minimizers, the $\\textit{guarantees}$ we prove (consistency) do handle approximate minimizers by definition. In contrast, proving them via calibration requires analyzing both exact and $\\epsilon$-optimal solutions (see Figure 1, pg. 2 of our paper for visual intuition).\n\n$$\\textbf{“Can the new surrogates certified by strong IE be trained effectively, and do they improve accuracy or calibration error on real data versus standard baselines?”}$$\nOur results apply to a broad class of convex, differentiable surrogates. These surrogates are well-supported by established training protocols with strong theoretical and empirical performance. For reliable accuracy/ target metric, a principled ML pipeline must ensure the surrogate is statistically aligned with the target loss—precisely what our IE and strong IE results guarantee.\n\n$$\\textbf{References}$$\n[1] P. L. Bartlett, M. I. Jordan, and J. D. McAuliffe. \"Convexity, classification, and risk bounds\". Journal of the American Statistical Association, 2006\n\n[2] J. J. Finocchiaro, R. Frongillo, B. Waggoner. \"An Embedding Framework for Consistent Polyhedral Surrogates\". NeurIPS 2019\n\n[3] Y. Wang and C. Scott. \"Weston-watkins hinge loss and ordered partitions\". NeurIPS 2020\n\n[4] J. J. Finocchiaro, R. Frongillo, E. Goodwill, and A. Thilagar. \"Consistent polyhedral surrogates\nfor top-k classification and variants.\" ICML 2022\n\n[5] J. J. Finocchiaro, R. Frongillo, and E. B. Nueve. \"The structured abstain problem and the lovász hinge\". COLT 2022\n\n[6] E. Nueve, D. Kimpara, B. Waggoner, and J. Finocchiaro. \"Trading off consistency and dimensionality\nof convex surrogates for multiclass classification\". NeurIPS 2024"}, {"review_id": "rB61E9vZUb", "reviewer": "Reviewer_3bYS", "summary": "With a multiclass output, verifying the consistency of a surrogate loss is a challenging task. The authors argue that examining the properties \"indirect elicitation\" and \"strong indirect elicitation\" provides insight on consistency. These two properties are easier to verify than consistency. Specifically, they prove that with when the input is one dimensional, consistency is equivalent to a property called \"Indirect Elicitation\", which essentially requires that distributions minimize surrogate are always included also minimize the target loss. However, this equivalence is false when the input is higher dimensional. In this case, a property called \"Strong Indirect Elicitation\" implies consistency. This property essentially requires that the set of minimizers of the surrogate is included in some intersection of sets of minimizers of the target loss. For strongly convex losses, strong indirect elicitation is equivalent to consistency.", "questions": "**Questions:**\n- Verifying consistency is simple in the two class case. See for instance Theorem 2 of [1], Theorem 3.1 of [2], or Theorem 2 of [3]. Can you give an intuitive explanation of why this is difficult for multiple classes?\n- Could you provide an intuitive explanation of what indirect elicitation and strong indirect elicitation entail?\n- I tried to working through Example 1 indepentently and found different behavior than what was described in the text. Specifically:\n$$ \\langle p, L(u)\\rangle=p_1( (1-u)^2+|u|)+p_2( (1+u)^2+|u|) ,$$ which is always minimized at zero. Could you clarify this calculation and provide further details?\n- Can you explain the intuition why the proof strategy of theorem 1 does not extend to the multi-input case?\n- Similarly, it would be helpful to emphasize exactly where Theorem 2 uses the property $\\gamma_S^*=\\{p:-\\gamma(p)=S\\}$, rather than $\\gamma_r=\\{p:r\\in \\gamma(p)\\}$.\n\n\n\n**Other Comments:**\n- line 63 should specify that this result is restricted to convex surrogates\n-Line 79: it would be helpful to discuss an example when $\\mathcal R\\neq \\mathcal Y$, such as classification with a reject option referred to later in the paper.\n-line 223: it would be helpful to explicitly state what $p$ is here\n\n\n\n[1] Peter L. Bartlett and Michael I. Jordan and Jon D. McAuliffe. \"Convexity, Classification, and risk bounds.\"\n[2] Yi Lin. \"A note on margin-based loss functions in classification\"\n[3] Natalie Frank. \"Adversarial Surrogate Risk Bounds for Binary Classification\".", "limitations": "Some losses don't have minimizers for all vectors $p$ in the simplex, see [1]. Some examples are the exponential loss for binary classification and the cross entropy loss on the simplex. How do your results apply to such losses?/ Is this solved via a link function?\n\n[1] Ambuj Tewari and Peter Bartlett. *On the Consistency of Multiclass Classification Methods*. JMLR. 2007.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**:\n**Quality and Significance:** This paper addresses a compelling problem-- understanding when studying minimizers of losses suffices to understand consistency. The results are convincing.\n\n**Weaknesses**:\n**Clarity:** There is a lot of technical notation and technical jargon in this paper that makes the results difficult to parse. I understand that the nature of this result is highly technical, but the authors could make this paper more patable by discussing the intuition surrounding the main objects of this paper.", "was_revised": true, "final_justification": "I maintain my score. As stated in my review, I believe this work makes a good contribution to the theory of surrogate risks. I think the biggest problem with this submission is its clarity. Through their comments, the authors have convinced me that they will work to improve the clarity of their paper prior to publication.", "rebuttal": "Thank you for your time and helpful feedback. We will improve and clarify the technical notation in the paper. We address specific concerns and questions below.\n\n$$\\textbf{“Verifying consistency is simple in the two class case. … Can you give an intuitive explanation of why this is difficult for multiple classes?”}$$\nIn the binary case, a scalar-score suffices for classification-calibration: it’s enough to determine whether $\\eta(x) = \\mathbb{P}(Y = 1 \\mid X = x)$ is above or below 0.5. For example, the derivative-rule from Bartlett et al. (2006) [1] states that a convex margin loss $\\phi$ is consistent w.r.t. $0-1$ loss iff it’s differentiable at $0$ with $\\phi'(0) < 0$. This condition ensures that the expected risk $\\eta(x)\\phi(t) + (1 - \\eta(x))\\phi(-t)$ decreases when $t$ moves in the correct direction away from $0$—negative if $\\eta(x) < 0.5$, positive otherwise. Thus, if $\\eta(x) < 0.5$, the minimizer $t^{\\ast}(x) < 0$, and the link $\\psi(t^{\\ast}(x)) = sign(t^{\\ast}(x)) = -1$ yields the correct prediction.\n\nIn contrast, no such scalar-derivative condition exists in the multiclass case. Even for $n = 3$, predictions depend on the full vector $\\eta(x) = [\\eta_1(x), \\eta_2(x), \\eta_3(x)]$, where $\\eta_i(x) = \\mathbb{P}(Y = i \\mid X = x)$. Suppose $\\arg\\max_i \\eta_i(x) = {3}$—then predicting class 3 is optimal for the $3$-class $0-1$ loss. At the uniform distribution $p = (1/3, 1/3, 1/3)$, we would want the surrogate loss’s gradient to decrease in all directions where coordinate 3 dominates and increase otherwise. This requires controlling an entire gradient field, not just a scalar.\n\nThe absence of a simple derivative-rule motivated the formal notion of calibration in Tewari and Bartlett (2007) [2]. But checking calibration remains difficult: as noted as well on page 5 of the seminal paper [2]. Doing so involves analyzing minimizing-sequences of the surrogate loss, which is hard in $\\geq$ 2D due to the uncountably many sequences surrounding the minimizer (see also Figure 1, pg. 2 of our paper for visual intuition).\n\n$$\\textbf{“Could you provide an intuitive explanation of what indirect elicitation and strong indirect elicitation entail?”}$$\nThe key advantage of IE and strong IE is that they depend only on surrogate minimizers, unlike calibration, which also requires reasoning about $\\textit{all}$ sequences converging to those minimizers (see Figure 1, pg. 2). Specifically, for any distribution $p$, calibration demands not only that the surrogate minimizer $\\Gamma(p)$ links to the target minimizer $\\gamma(p)$, but also that $\\textit{every sequence}$ converging to $\\Gamma(p)$ eventually links to $\\gamma(p)$. IE only requires ensuring that $\\Gamma(p)$ links to $\\gamma(p)$. \n\nFor geometric intuition: IE holds if each level set $\\Gamma_u$ lies entirely within a target-cell. As illustrated in Figure 3 (pg. 6 of our paper), the level set $\\Gamma_{0,0}$ (blue line) violates IE by crossing from $\\gamma_{1}$ into $\\gamma_{2}$ (left figure), and satisfies IE by lying entirely within $\\gamma_2$ (middle figure). However, because it $\\textit{touches}$ the red boundary between $\\gamma_1$ and $\\gamma_2$, strong IE is violated. Strong IE strengthens IE by requiring that level sets be fully contained and $\\textit{also bounded away}$ from target boundaries (right figure).\n\n$$\\textbf{“I tried to working through Example 1 indepentently … Specifically: $\\langle p, L(u) \\rangle = p_{1}((1-u)^{2} + |u|) + p_{2}((1+u)^{2} + |u|)$, which is always minimized at zero.”}$$\nThank you for cross-checking. The expected loss $p_1((1 - u)^2 + |u|) + p_2((1 + u)^2 + |u|)$ is only minimized by $u=0$ for distributions in the set $\\\\{p \\in \\Delta_2: \\max{p_1, p_2} \\leq 0.75 \\\\}$. For instance, if $p_1 = 1, p_2 = 0$, the expression becomes $(1 - u)^2 + |u|$, which is minimized at $u = 0.5$.\n\n$$\\textbf{“Can you explain the intuition why the proof strategy of theorem 1 does not extend to the multi-input case?”}$$\nThe proof of Theorem 1 assumes the existence of a 1D convex surrogate that indirectly elicits the target—an assumption that holds $\\textit{only}$ for orderable targets (see Proposition 27, pg. 17 of [3]). It therefore leverages structure specific to orderable losses. In contrast, Theorem 2 addresses general, non-orderable targets, requiring a fundamentally different proof technique to handle full generality.\n\n$$\\textbf{“It would be helpful to emphasize exactly where Theorem 2 uses the property… ”}$$\nThe property you're referring to is strong IE (Definition 6, pg. 7) and is used in Lemma 29 (pgs. 24–25) to prove Theorem 2. Intuitively, strong IE, combined with properties of the set-valued map $\\Gamma_{(\\cdot)}$, ensures that minimizers of distributions near $\\Gamma_u$ don't link to reports incompatible with $u$ (for any surrogate report $u$). We will make this explicit.\n\n$$\\textbf{Other Comments, regarding lines  63, 79 and 223}$$\nThank you for pointing these out. We will be sure to incorporate your feedback. \n\n$$\\textbf{“Some losses don’t have minimizers for all vectors in the simplex … How do your results apply to such losses?/ Is this solved via a link function?”}$$\nThe losses you mention—e.g., cross-entropy—are minimizable in the interior of the simplex but not on its boundary. Our results apply wherever minimizers exist, i.e., in the interior. At boundary distributions IE/strong IE conditions don’t apply. In such cases, one must consider minimizing sequences, and we conjecture that addressing these cases in full-generality may require tools from the emerging theory of astral spaces ([4]).\n\n$$\\textbf{References}$$\n[1] P. L. Bartlett, M. I. Jordan, and J. D. McAuliffe. \"Convexity, classification, and risk bounds\". Journal of the American Statistical Association, 2006. \n\n[2] A. Tewari and P. L. Bartlett, “On the Consistency of Multiclass Classification Methods.” JMLR. 2008\n\n[3] J. Finocchiaro, R. Frongillo, and B. Waggoner. \"Embedding dimension of polyhedral losses\" COLT 2020\n\n[4] M. Dudík, R. E. Schapire, and M. Telgarsky. “Convex analysis at infinity: An introduction to astral space.” 2022"}]

Author rebuttal:

Meta-review: I am recommending this paper for publication. The reviewers all agree that the technical contribution is strong. Specifically that IE is equivalent to calibration is a strong result, I suggest authors work on improving the presentation as mentioned by the reviewers.
Decision: Accept (poster)