Trading off Consistency and Dimensionality of Convex Surrogates for Multiclass Classification
Authors: Enrique Nueve
Dhamma Kimpara
Bo Waggoner
Jessica Finocchiaro
Venue: NeurIPS 2024 poster (2024)
Keywords: Loss Functions
Consistency
Property Elicitation
Primary area: learning_theory
TL;DR: This work explores theoretical guarantees for partial consistency when violating known prediction dimension bounds.

Abstract: In multiclass classification over $n$ outcomes, we typically optimize some surrogate loss $L: \mathbb{R}^d \times\mathcal{Y} \to \mathbb{R}$ assigning real-valued error to predictions in $\mathbb{R}^d$. In this paradigm, outcomes must be embedded into the reals with dimension $d \approx n$ in order to design a consistent surrogate loss. Consistent losses are well-motivated theoretically, yet for large $n$, such as in information retrieval and structured prediction tasks, their optimization may be computationally infeasible. In practice, outcomes are typically embedded into some $\mathbb{R}^d$ for $d \ll n$, with little known about their suitability for multiclass classification. We investigate two approaches for trading off consistency and dimensionality in multiclass classification while using a convex surrogate loss. We first formalize partial consistency when the optimized surrogate has dimension $d \ll n$. 
We then check if partial consistency holds under a given embedding and low-noise assumption, providing insight into when to use a particular embedding into $\mathbb{R}^d$. Finally, we present a new method to construct (fully) consistent losses with $d \ll n$ out of multiple problem instances. Our practical approach leverages parallelism to sidestep lower bounds on $d$.

Trading off Consistency and Dimensionality of Convex Surrogates for Multiclass Classification
Enrique Nueve
Bo Waggoner
Department of Computer Science University of Colorado Boulder enrique www.iiuueeeeeeiiieeeemmmeee nueveivêee www.eiiveoooraooooooooooo edu
Department of Computer Science University of Colorado Boulder swag@coloratd edu
Dhamma Kimpara
Jessie Finocchiaro" Department of Computer Science Boston College f finocch@bc.cm edu
Department Computer Science
University of Colorado Boulder
dhamma wwwpara@colooaeeeeeocoaoooo edu
Abstract
In multiclass classification over n outcomes, we typically optimize some surrogate loss L Ra y + R assigning real-valued error to predictions in R In this paradigm, outcomes must be embedded into the reals with dimension d z n order to design consistent surrogate loss. Consistent losses well-motivated theoretically, yet for large n, such as in information retrieval and structured pre- diction tasks, their optimization may be computationally infeasible. In practice, outcomes are typically embedded into some I2d for d < nt, with little known about their suitability for multiclass classification. We investigate two approaches for trading off consistency and dimensionality multiclass classification while using convex surrogate loss. We first formalize partial consistency when the optimized surrogate has dimension d < n. We then check if partial consistency holds under given embedding and low-noise assumption, providing insight into when use a particular embedding into Rd Finally, we present a new method to construct (fully) consistent losses with d < n out of multiple problem instances. Our practical approach leverages parallelism to sidestep lower bounds on d.
Introduction
Multiclass classification, due its combinatorial and discontinuous nature, is intractable optimize directly, which drives machine learners to optimize some nicer surrogate loss. To ensure these surrogates properly "correspond" to the discrete classification task, seek design consistent surrogates. If one uses a consistent surrogate loss, in the limit of infinite data and model expressivity, one ends up with the same classifications as if one had solved the original intractable problem directly with probability 1.
Surrogate losses form the backbone of gradient-based optimization for classification tasks. Optimizing a surrogate easier than direct optimization, but large dimension d of the surrogate loss Rd y R can make gradient-basee optimization intractable. Therefore, previous literature has operated under the premise that the prediction dimension d should be as low as possible, subject to consistency for the classification task [Ramaswamy and Agarwal, 2016, Finocchiaro al., 2024, 2020]. For multi-class classification over n outcomes, the lower bound on d n 1 [Ramaswamy and Agarwal, 2016).
Most of this work completed while author Harvard University CRCS
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

These previous works implicitly focus on a binary approach to consistency: a surrogate is either consistent for every possible label distribution, or is not consistent. But there way out: lower bounds on the surrogate dimension d rely on edge-cases that rarely show up in reality [Ramaswamy and Agarwal, 2016]. As a result, practitioners are often willing to trade-off the guarantee of con- sistency in order to improve the computational tractability of optimization. However, we currently lack rigorous analysis tools to analyze many of the partially-consitten surrogates commonly used in practice. Thus, unlike previous works, our work focuses this more realistic paradigm of partial consistency. We apply our unique approach to rigorously analyze a popular surrogate construction that encompasses methods such one-hot and binary encoding. Our approach allows for fine- une-grained control of the trade-off between consistency and dimension.
Prior works have informally brushed upon the proposed cartial-consisteney paradigm, without rigorous study. For example, Agarwal and Agarwal [2015] impose a low-noise assumption to construct a surrogate for classification with d = log(n.) However, their work does not provide any trade-off. Similarly, Struminsky et al. [2018] characterize
way to control the beasiitency-dimensee the excess risk bounds of inconsistent surrogates, which teaches about the learning rates for inconsistent surrogates, but not under which distributional assumptions we can recover consistency guarantees.
Using different techniques than both of these approaches. we seek understand the tradeoff's of consistency, surrogate prediction dimension, and number of problem instances through the use of polytope embeddings which are common in the literature [Wainwright et al., 2008, Blondel et al., 2020]. When embedding outcomes into d & n dimensions, we first show there always exists set of distributions where hallucinations occur: where the report minimizing the surrogate leads to prediction ý such that the underlying true distribution has no weight on the prediction; that is, Pr[Y = 0] = 0 (Theorem 3). Following this, we show that every polytope embedding is partially consistent under strong enough low-noise assumptions (Theorem 5). Finally, we demonstrate through leveraging the embedding structure and multiple problem instances that the mode (in particular, a full rank ordering) over outcomes embedded into a n dimensional surrogate space is elicitable over all distributions via O(n²) problem instances (Theorem 10). This alternative approach to recovering consistency is parallelizable, detangling the complexity of gradient computation of one high-dimensional surrogate.
2 Background and Notation
Let y be finite label space, and throughout let n = 13%. Define R. to be the nonnegative orthant.
V, represented as vectors. We denote the point mass distribution of an outcome y E y by 6, E Ay. Let [d] := {1..... d}. In general, denote discrete loss by L y x y R2 with outcomes denoted by y E y and surrogate loss by L Rdd x x + R with surrogate reports u E Rd and outcomes y E y. The surrogate must be accompanied by link th Rd -> y mapping the convex surrogate model's predictions back into the discrete target space, and we discuss consistency of a pair (L, v)) with respect to the target E.
Let Αy {p R. ||pl| 1} be the set of probability distributions
For E > 0, we define an epsilon ball via (u) = {a e Id | ||u - æ112 < <} and B : B.) Given a closed convex set C C Rd. we define a projection operation onto via (roje(u) = arg minzec I|u fu==1122- Given a closed convex set C C Rd and E Rd, we let the set-pointwise distance to be defined as ||u - Cl|2 == I|u Proje(u)ll2. Full tables of notation are found in Appendix A.
x112-
2.1 Property Elicitation, Consistency, and Prediction Dimension
Discrete label prediction requires optimization of a target loss function, f, e.g. multi-class classifica- tion and 0-1 loss. When designing surrogate losses, consistency is the key notion of correspondence between surrogate and target loss. Intuitively, consistency implies that minimizing surrogate risk cor- responds to solving the target problem. Finocchiaro et al. [2021] show that surrogate loss consistency a necessary precursor to excess risk bounds and convergence rates.
Consistency is generally a difficult condition to work with directly. Hence, we will use the notion of calibration, which equivalent to consistency in our setting with finite outcomes. Our approach follows from the property elicitation literature, which allows us to abstract away from the feature space

---

X' and focus on the conditional distributions over the labels, Pr/Y X Ay [Bartlett al., 2006, Tewari and Bartlett, 2007, Zhang. 2004, Ramaswamy and Agarwal, 2016, Steinwart, 2007]. In this approach, the central object of study is property which maps label distributions to reports that minimize the loss.
Definition 1 (Property, Elicits, Level Set). Let R be arbitrry report set. For P S Ay. a property is a set-valued function I: P + 2R \ {00), which we denote I = y. A loss L R x y elicits the property T on P if
vp P, r(p)= arg min By (y
wER
If elicits property, it is unique and we denote it prop T... The level set Tf for report is the set : {p E ' 1 [p))) If prop([. L]] = and [T()]] = for all E P, we say that T. is strictly proper r.
In this work, R y for target losses and R = Rdd for surrogate losses.
Once model is optimized wrt. a surrogate T,, it predicts reports in the surrogate space, Rd. Then, to map surrogate reports to discrete labels, the surrogate loss must be paired with link, 3/ R -> y Intuitively, surrogate and link pair (L, vi) are calibrated with respect to target loss f, if the optimal expected surrogate loss when making the incorrect classification (by v) is strictly greater than the optimal surrogate loss.
Definition 2 (E-Calibrated Loss). Given discrete loss E: y x - R2, surrogate loss L R x y R, and link function 1b Rdd -> y. We say that (L, 1b) is E-calibrated over P [ Ay if. for all p P.
inf (eproplt [v, Y)] inf Ey-plL(u, Y)..
wER"
P not specified, then we are discussing calibration over Dy. In general, when (L, v) is l-calibrated over P such that P C Ay, we say partial calibration holds with respect to P.
Our analysis crucially relies the ability to specify P when invoking the definition of calibration. This is because the surrogates we analyze break the d = n lower bound on the dimension of any consistent surrogate loss. So the surrogates will not be calibrated over the whole simplex Ay. To aid in our analysis, we use a condition that shows that converging to a property value implies calibration for the target loss itself [Agarwal and Agarwal, 2015].
Definition 3 (f-Calibrated Property). Let S Dy, I P = Rd, discrete loss E: Y x ) - Rt, and &b Rd + V. We will say (T, v) is E-calibrated for all p E P and all sequences { in RR if.
Um + r(p) + (ymple(sb(um)) Y) + min BrinEr>ple(r: Y)]
rEY
Theorem ([Agarwal and Agarwal, 2015, Theorem 3)). Let E. y x y - R4 and P C Ay. Let T: P = Fd and & Fd + y be such that is elicitable and (T, v) an l-calibrated property over P. Let L Rd x y + R be convex function for all y y and strictly proper for I i.e. prop[[] - and [Tp] = 1 for all E P. Then, (L, 1) is l-calibrated over P.
Finally, we present the 0-1 1 loss that analyze, which is the target loss for multiclass classification. Definition 4 (0-1 Loss). We denote the 0-1 loss by fo-1 y x y > {0, 1} such that fo-1 (y: 0) = lyzg. Observe dasterveymma mode (p) == prop[fo- = ty E Vly E arg max, py
3 Polytope Embedding and Existence of Calibrated Regions
Often, discrete outcomes embedded in continuous space onto the vertices of the simplex via one-hot encoding, or the vertices of the unit cube via binary encoding [Seger, 2018J. Generalizing, we introduce an approach to surrogate construction inspired by Wainwright et al. [2008] and Blondel et al. [2020] that encompasses the aforementioned embedding methods. This construction utilizes embeddings onto the vertices of arbitrary -ww-dinensiona polytopes & y Rd Then, an embedding scheme naturally induces a large class of loss functions L defined by the embedding, any G-Bregman Divergence, and link function w/.
Our analysis begins by defining condition stronger than inconsistency that arises when embedding into d < n 1 dimensions for multiclass classification. To this end, we introduce the notion of
3

---

hallucination as a means to characterize the "worst case" behavior of surrogate pair ($ 3.2). In positive manner, we characterize the calibration regions of various embeddings ($ 3.3). which are sets P C Ay such that our surrogate and link pair (I.g. 169) are {-calibrated over P. We refer the reader to the Appendix B for omitted full proofs.
3.1 Polytope Embedding Construction
Convex Polytope P C R", or simply a polytope, is the convex hull of a finite number of points W1,...y un Rd An extreme point of convex set A, a point u A such that if u. = xy + (1- with y, E A and À E [0, 1), then y = w and/or = = u. We shall denote by verl(P) a polytope's set of extreme points. A polytope can be expressed by the convex hull of its extreme points, i.e. P = conv (vert(P)) [Brondsted, 2012, Theorem 7.2]. Additional defimitions pertaining to polytopes are used for proof's that are omitted to the appendix, we refer the reader (8 B.1) for said definitions.
We propose the following embedding procedure that allows one to construct surrogate losses with almost any polytope, and any Bregman divergence.
Construction (Polytope Embedding). Given y outcomes, [V] = n, choose a polytope P C TRd such that |ver((P)] = Choose bijection between Y and vert(P). According to this bijection, assign each vertex a unique outcome that {uy E By E }} vert(P). Then the polytope embedding & Ay + P sp()) == EyeyPp" which is the sum of p-scaled vectors
Following the work of Blondel [2019] and their proposed Projection- baaeed losses, we use the extremely general class of Bregman divergences (Definition 5) and a polytope embedding to define an induced loss _ (Definition 6).
Definition 5 (Bregman Divergence). Given a strictly convex function G Rd + R. Da(u, v) == G(v) (D [G(u) + (dGr, u 2)} is a Bregman divergence where dG,, denotes subgradient of G For this work, we shall always assume that dom(G) = -Rdd.
Definition 6 (DDa,9) 4) Induced Loss). Given a Bregman divergence Da and a polytope embedding s, we say (Do. (p) induces a loss LG Rdd x - R. defined as
[u(,)) == -a(u,, 0y) G(v,) - [G(u) + (dCte u vyyl
Note, that any fixed y y, LG (u. y) is convex with respect to E Rd.
We show that for any p Ay, the report that uniquely minimizes the expectation of the loss L is (p()), the embedding point of p. Furthermore, the polytope P contains all of, and only the minimizing reports in expectation under T.G.
Proposition 2. For given induced loss L.G the unique report which minimizes the expected loss n² arg min By (T.plT (u, Y)] = p(p) such that u² P. Furthermore, every â P is
minimizer of /y L (u, Y) for some p E Ay.
We now define the maximum a posteriori (MAP) link which will be used in conjunction with an induced loss L to form surrogate pair for the 0-1 loss. The MAP link projects surrogate predictions onto the polytope P, then links to the nearest vertex of P. and is commonly used in the literature [Tsochantaridis et al., 2005, Blondel, 2019, Xue et al., 2016]. Since the MAP link performs projection, one may ask if this is computationally challenging; fortunately this operation computationally feasible due the convexity of the polytope [Blondel, 2019].
Definition 7 (MAP Link). Let yp be a polytope embedding from Dy to P. The MAP link v/1 Rd y defined as e) arg min (() vyll2. The level set of the link for y is U/P- = {u E Rdly = x/ (u)}. We break ties arbitrarily but deterministicall:
3.2 Hallucination Regions
Since our polytope embedding violates surrogate dimension bounds, calibration for 0-1 loss will not hold for all distributions. In particular, we show there always exists some distribution p such that Py = 0 yet Ey Sx Y)] is minimized at some such that (1) y. This implies "worst case" inconsistency where the reported outcome could never actually occur with respect to our embedding of n events via so into vert(P).

---

b
a
d
a
ad
acd
abd
f
C
cd
bed
ab
abe
bc
b
e
d
Figure I: (Left) Mode level sets of Ay where y =- (a, e, d) embedded into a two dimensional unit cube. The center red point denotes the origin (0,0) which is the hallucination region. (Right) An embedding of Ay where y {a, b, e, d, e, e) into three-dimensional permutahedron: the beige region expresses strict calibration regions, the light pink regions expresses regions with inconsistency, and the auburn region expresses regions with hallucinations. For example, consider the report Ö. Since losses are convex, if p = (0, 1 0, 0, 3. 0), then conv (1b, e}) (dashed grey) is optimal, which includes u. However, 0 is also contained in conv (fa, d}) which is optimal for the distribution p' 0, 1, 0). Therefore, cannot distinguish the optimal reports for hallucination at Ö.
d < n, and db Rd +Y, y, we say that hallucination occurs at a surrogate report u E R. if. for some Dy, arg min Ey-pl [L, Y)] and vb()) := y but Py
Definition 8 (Hallucination)). Given (L, v) such that L R2 X - R+,
We denote by H. S P R as the hullucination region as the elements of P at which hallucinations can occur.
We express the subspace the surrogate space where hallucinations can occur as the hallucination region denoted by H. In Theorem 3, characterize the hallucination region for any polytope embedding while using the surrogate pair (I.g. 1/P) and show that H is never empty.
Theorem 3. For any given pair (LG, viP) and fo-1 with embedding dimension that H Uyeyyonv (vert(P) \ {vy}) n rhf and furthermore H & Ø.
it holds
Sketch. Fix y E V. We abuse notation and write vert(P-,, == vert(P) { Observe conv (vert(P-w)) n oy S H since any point in this set be expressed convex combina- tion without needing vertex by implying there is a distribution embedded by to said point which has no weight y. We seek to show that H. C Upeyconv (vert(P-y)) n 1pÿ. Assume there exists point u & conv (vert(P) (yy n vo such that there exists some Ay where (p() and (p) y. Since (1) y and u conv (vert(P-y)) r/f. it must be the case that conv (vert(P-,)). However, that implies that is strictly in the vertex figure and thus must have weight on the coefficient for y. Thus, forming a contradiction that Py = which implics that H. C Uyeyconv (vert(P-,)) n wif. Finally, using Helly's Theorem [Rockafellar, 1997, Corollary 21.3.2] we show that Nyeyconv (vert(P) vy)) + Ø, which implies the non-emptiness of H as well.
Py 0,
Theorem 3 suggests that using machine learning in high-risk settings such as medical and legal applications while violating the known classification is inherently ill-advised without human intervention given the possibility for hallucina- tions. Furthermore, hallucinations may be forced by the target loss, in the of Hamming loss (see Appendix C). In these cases practitioners should carefully consider the choice of target loss. We conjecture that hallucinations are common for many structured prediction losses. However this not a concern in our primary loss of study of multi-class classification.
dimensional bound for surrogate losses in multiclass
3.3 Calibration Regions
Ideally, we would like calibration to hold over the entire simplex since that would imply minimizing surrogate risk would always correspond to solving the target problem regardless of the true underlying
5

---

distribution. We observe that the mode's embedded level sets in the polytope overlap (see Figure IL), which is unsurprising given that we are violating the lower bounds on surrogate prediction for the mode and hence calibration does not hold over the entire simplex. Since 22 { is a finite set, we know that the number of unique mode level sets is finite. Although every point in the polytope is a minimizing report for some distribution, if multiple distributions with non-intersecting mode sets are embedded to the same point, there is no way to define link function that is correct in all cases. However, if the union of mode sets for the p's mapped to any E P is singleton, regardless of the underlying distribution?, a link would be calibrated over the union if it mapped u to the mentioned singleton. Given (L, 1b), ip, and target loss L, we define strict calibrated regions the points for which calibration holds regardless of the actual distribution realized, which are possible at said points.
Definition 9 (Strict Calibrated Region). Suppose we are given (L, 1), ?, and a target loss f. We say R C P is strict calibrated region via (I, 1b with respect to E if (L, 1) is E-calibrated for all p E 4 1 Rt) == {p E Ay (p))= E R).
For any y E y, we define Ry == R n By. We let Ry == Ryey
By violating lower bounds, we are in partially consistent paradigm where surrogate reports do not necessarily correspond to a unique distribution However, strict calibration regions allow to check whether or not the loss is calibrated for the distribution p generating the data - even without explicit access to p. One simply has to check whether the report is in Ry.
In Theorem regardless of one's chosen P. we show that there always exists a non-zero Lebesgue measurable strict calibration region and that (LS) x/9) is calibrated for the 0-1 loss overall distri- butions embedded into the strict calibration region. This result shows that our surrogate and link construction for any d, always yields discernible calibration regions - lending support to the practical use and study of these surrogates.
Theorem 4. Let De be a Bregman divergence, ip be any polytope embedding. v be the MAP link, and _ be the loss induced by (Da, p). There exists a P C Ay with non-zero Lebesgue measure and (pP) S Ry via (LG. ())) with respect to fo-1-
Although strict calibration regions Ry exist for each outcome y E y/ via the polytope embedding, tightly characterizing strict calibration regions is non-trivial. Since the level sets of elicitable properties are convex within the underlying simplex, characterizing the strict calibration regions becomes a collision detection problem, which is often computationally hard.
Restoring Inconsistent Surrogates via Low-Noise Assumptions
Looking towards application, we refine our results on the existence of strict calibration regions by examining a low-noise assumption, which provides an interpretable calibration region ($ 4.1. We show which low-noise assumptions imply calibration when embedding 2d outcomes into d dimensions and d! outcomes into d dimensions ($ 4.2). We refer the reader to Appendix B for omitted proofs.
4.1 Calibration via Low Noise Assumptions
We demonstrate that every polytope embedding leads to calibration under some low-noise assumption. Our results enable practictioners to choose the dimension d, unlike in previous works. Following previous work [Agarwal and Agarwal, 2015], we define a low noise assumption to be a subset of the probability simplex on the label distribution parameterized by â: O = { E Ay max Py > 1 â) where & [0, 1). This noise assumption can be understood as Massart noise [Massart and Nédélec, 2006] in the multiclass setting.
Given a E [0, 1] and y E Y, we define the set v = {(1-a)6, + aag و E V). With an embedding onto P. we define the set Py == sp(covv (V&)), scaled version of P anchored at ey, that moves vertices (1 - a) proportionally towards y. (Figure 2R).
Theorem 5. Let DG be Bregman divergence, ip be any polytope embedding, and L be the loss induced by (Dc, There exists an [0, 5)) such that for the link (U) arg min I|u pllla, (LS, sp9-r) is fo-1-calibratee over the distributions Q. := {p E Ay max Py 2 1 a}.
We leave the more general case of linking when OPep 1(1) T() * Ø to future work.

---

Proof. Part (Choosing a E (0, x By Theorem 4, there exists an e >> 0 such that (U,) (2)) Ry for all y V. Given that vPr are unique points, there exists a sufficiently small é' > 0 such that (v) n (e) Ø for all n, 0 E vert(P) where v & à. Let e" = min (c, For any y E y/ observe the set conv (v2), defined using any a E [0, is a scaled-down translated unit simplex and that for all p E conv (V2) C Ay it holds that y mode(p).
We shall show that for some sufficiently small a [0, P is scaled down version of P positioned at the respective vertex By. Furthermore, we shall show that Pa C (ey( n. C Ry for all y E y. Observe that by linearity of pp
PH = pf(cov (V)) = conv (c(((( 06 + adggú E )})) - conv ({(1 a)uy + oug lú E }}}
and hence, Pω is a scaled version of P positioned at uy. Hence for some sufficiently small a, (1 - a)v, + aug (ry ( for all and hence P4 C (uy(( C CRy. With said sufficiently small a, define v/ and the respective sets conv (V%) for each y E y. Using the previous a, define the set O, as well.
Part 2 (Showing Calibration): Recall, by Proposition 2, for any p E Ay, u = (p(p) minimizes the expected surrogate loss Ey~pl [ E (u, Y)]. For any fixed y E V, observe that conv - ((1-))6, adg
ÿ E y = {p E Ay : Py 2 1 - a) C Ay and hence, by Proposition 2, Uyey Pd contains all of the minimizing surrogate reports with respect to θ,, By our choice of a and the construction of viP every u E UpEy Pa is linked the proper unique mode outcome since UyEyP% C Ry- Assuming a low-noise condition where E ①... any u é Py is never optimal for any low-noise distribution. In such cases, we project the point to the nearest P8 as matter of convention. Given that calibration is result pertaining to minimizing reports, this design choice is non-influential Finally, since every UyEyPe Pa C Ry. by the definition of strict calibration region, holds that (L v/P.a) is fo-1 calibrade for θ...
4.2 Embedding into the Unit Cube and Permutahedron under Low-Noise
In this section, we demonstrate embedding onto the unit eube and the permutahedron [Blondel et al.. 2020, Seger, 2018]. We show that by embedding 2d outcomes into d dimensional unit cube p=) (IC, 1 v ()) is calibrated over O, for all a E [o, }). Furthermore, we found that by embedding d! outcomes into a d dimensional permutahedron p (I. v/P .)) is calibrated for O for a E [0, 4). Theorem enables us to simultancously study the aforementioned embeddings.
Theorem 6. Let DG be a Bregman divergence, yp be any polytope embedding. and LS be the (0) and with it define O If for all y. E y such that + ÿ it holds that Py n Pa = Ø. then (I.), ()0.)) is ta fo-1-calibrated for Oa where apria arg min - P
loss induced by (Da, sp). Fix
Proof. Pick an a such that for all y. E y PX Ø. Define θ, and ap accordingly. For E O, and some y E y, say sequence } converges to prop prop(T.g(pp) = ppp) E Py where the cquality follows from Proposition 2. Given that each P is closed and pairwise disjoint, there exists some é such that for all y. ÿ E y where y * ÿ. it also holds that (P" + Ba) (På + Ba) = 2 where + denotes the Minkowski sum. Since {um converges to ((p), there exists some N E N such that for all n Z N, ||4, (p)) < By the definition of wi any Un where > N will be mapped to y. the correct unique report given that prop[T-g]e (p) E Pg. Hence, (prop) [. 10P/)) is fo-i-calibrated property with respect O Finally, since I. is strictly proper for prop [L by Theorem 1, we have that (I.G, vp is ca-i-calibrated for θ...
Unit Cube Define a unit cube in d-dimensions by p == conv (1-1, Binary encoding outcomes into the elements of { 1-1, 1d (the vertices of a unit cube) is commonly used method in practice (e.g., [Seger, 2018, Yu and Blaschko, 2018]). We show that calibration holds under a low noise assumption of O,, when a < .5.
Corollary 7. Let be an embedding from 2 outcomes into the vertices of pil in d-dimensions and define induced loss Lg. Fix E [0, and define O... (L) 20P000) " is fo-1--1-100 -o-l-calibaated for e..
7

---

b
d
a
f
d
Sa}) I.d The permutahedron may serve Figure 2: (Left) Corners represent the strict calibration regions for O where y = fa, b, c, d} is embedded into two dimensional unit cube such that .25. (Right) Auburn regions show that strict calibration holds for +,, where y = {a, b, d, e, . } is embedded into a three-dimensional permutahedron such that a
Corollary suggests that binary encoding is appropriate methodology when one has prior over the data that the mode of the label distribution Pr[Y = æ] is greater than half for all æ E X. Interestingly, the bound of a is not dependent on the dimension of d. We now present a result for embedding outcomes into factorially lower dimension via the permutahedron. Intuitively, ranking can be recast as multiclass classification problem, in which case the outcomes are orderings of the possible labels.
Permutahedron Let Sy express the set of permutations on [d]. The permutahedron associated with a vector w E IRd defined to be the convex hull of the permutations of the indices of w, i.c. p" := conv (fr(w) outcomes into d-dimensions; is a natural choice for embedding full rankings over items.
embedding from d!
Corollary 8. Let yp be an embedding from d! outcomes into the vertices of p d dimensions
such that (0, 1 2 caal-cabibrated over θ,,
d-1) RRd where = 1_1 Fix a E [0, 4). Then (L ob" " a) is
3d
The calibration region in Corollary 8 show that consistency in O, shrinks exponentially in d. Unless one has prior that the data follows some form of power distribution, Corollary suggests not to factorially embed outcomes.
5 Elicitation in Low Dimensions with Multiple Problem Instances
The tools developed in previous sections now enable to address the setting in which require full consistency, P = Ay. but also desire surrogate prediction dimension d < n - 1. We side-step the 1 lower bound by utilizing multiple problem instances and aggregation of the outputs. Although cumulatively we have a larger surrogate prediction dimension than n - 1, each individual problem surrogate prediction dimension. This approach is well-motivated since
instance has less than allows for distributed computing of separate, smaller models which leads to faster convergence overall since in general optimization is least poly(d), Previous work such Ramaswamy et al. [2014) has explored the consistency of multiclass problem reductions; however, we take different, geometrically motivated, approach.
Definition 10. Extending Definition I, say loss and link pair (T,,4), where L. Rd x x and 1b gd + }, elicits property 1 P = on P C By if P. l(pp) (arg min,er= [y=p[[(u,
Definition 11 (nn, d, -ooloyttoee Elicitable). Suppose we are given a property < = such that P P Ay and | finite outcomes. Say have unique polytope embeddings {4p : Dy 1 where d <
1, and set of induced losses {L ym and links 3b Rdd - B, defined
wrt. 92 where B, is an arbitrary report set. For each j E [m], assume the pair (LC, vb)) elicits the property T P 3 By. If there exists a function T B, x ... x Bm = y such that for any p E Dy it holds that T (p).... .... I'm (p)) = 7()), say that y is (n, d, -Polytoo Elicitable over P.
8

---

C
b
C
d
d
b
Figure 3: Four outcomes embedded in R2 in different ways, with the minimizing reports for distribution p." (Left) Configuration ;p; with at (-.,, .3) implying > Pa and > Pe- (Right) Configuration y22 with at (0, 0) implying pa ps and pe = Pa. This implies the true distribution is (0.4, 0.4, 0.1, 0.1)."
Equivalently, we will also say that the pair (1(4 by)) T) (n, d, erty y with respect to P.
m))ddd,)Popppeee Polytope elicits the prop-
We shall express a d-cross polytope by p == conv (1,1 0)) a E Sa)) where (+1,0,..... 0) E TRd. Observe that a d-cross polytope has 2d vertices. For any vertex of d-cross polytope vert( (P)), we shall say that (v,-0) uu) forms diagonal vertex pair.
given cross pross-polytope embedding sp Aad + p and induced loss L Let (Va, )o;), be the ith diagonal pair (i.e. :0(ōa)) vai). Define the property D A2d - B element-wite by
Lemma 9. Say
<, as bb) ai bi) asybi b:)
if Pa. pb.
rP(p);
Pa. Pb. if, = pb.-
Furthermore define the link Po
Rd with respect to each diagonal pair as
as bi)
if Ilu Va, ||2 Iu Ub, ff va l2 < Cb
Vau Vors vb t
as, bi)
as. bi)
Then (L R elicits I'f
The following theorem states that by using multiple problem instances, based on Lemma 9, we can Polytope-elichs the mode. Algorithm outlines how aggregate the individual solutions infer the mode. We defer the proof to Appendix B.
Theorem 10. Let d 2 2. The mode (2d, d, m)-Polytope Elicitable for some m E 12d- d(2d 1)].
Algorithm Elicit mode via comparisons and the dl-Cross Polytopes
Require: M = {(LS w.5 }mm
Learn a model hy X' + Rd for each instance (LG, v E M
For some fixed x E X. collect all Bj + wp (hy(x)) where BN E B, Report R FindMaxes" (R (B,..., Bm))
Although Theorem 10 states that the mode is (2d, d, m) PPllytoe Elicitable for some m E [2d 1, d(ddd 1)]. it does not state how select said { ワ,, v. ) problem instances in optimal manner. Unfortunately, selecting the min number of problem instances reduces to minimum set cover problem which computationally hard. Even so, through a greedy approach, one can choose
'Given all comparisons, sorting algorithm can be used to compute the set of r E y such that p. is maximum.

---

problem instances that are log approximate optimal relative to the true best configuration. In practice using real data, given that these are asymptotic results, we may have conflicting logic for the provided individual reports. In Appendix D, we discuss an approach of how to address this in practice.
6
Discussion and Conclusion
This work examines various tradeoffs between surrogate loss dimension, restricting the region of consistency in the simplex when using the 0-1 loss, and number of problem instances. Since analysis is based on an embedding approach commonly used in practice, our work provides theoretical guidance for practitioners choosing embedding. We several possible future directions. The first is a deeper investigation into hallucinations. Future work could investigate the size of the hallucination region in theory, and the frequency of reports in the hallucination region in practice. Another direction would be to construct a method that efficiently identifies the strict calibration regions and the distributions embedded into them. This would provide better guidance whether or not a particular polytope embedding aligns with one's prior over the data. Another possible direction would be to explore whether concepts from this paper could be applied to the underlying problem of cost-sensitive multiclass classification. Finally, another direction is to identify other properties that can be elicited via multiple problem instances while also reducing the dimension of any one instance.
Broader Impacts: Our work broadly informs the selection of loss functions for machine learning. Thus our work may influence practitioners' choice of loss function. Of course, such loss functions can be used for ethical or unethical purposes. We do not know of particular risks of negative impacts of this work beyond risks of machine learning in general.
Acknowledgments and Disclosure of Funding
We thank Rafael Frongillo for discussions about hallucinations, which led to the exploration of many of the ideas in this work and Amzi Jeffs for discussions regarding convex geometry. This material is based upon work supported by the National Science Foundation under Award No. 2202898 (JF).
10

---

References
Arpit Agarwal and Shivani Agarwal. On consistent surrogate risk minimization and property elicitation. In Conference on Learning Theory, pages 4-22. PMLR, 2015.
Arindam Banerjee, Xin Guo, and Hui Wang. On the optimality of conditional expectation as
bregman predictor. IEEE Transactions on Information Theory, 5177):264666, 2005.
Peter L Bartlett, Michael Jordan, and Jon D McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):138-155 2006.
Mathieu Blondel. Structured prediction with projection oracles. Advances in neural information
processing systems, 32, 2019.
Mathieu Blondel, André FT Martins, and Vlad Niculae. Learning with fenchel-young losses. The Journal of Machine Learning Research, 21(():1314-1382, 2020.
Ame Brondsted. An introduction to convex polytopes, volume 90. Springer Science & Business Media, 2012.
Jessie Finocchiaro, Rafael Frongillo, and Bo Waggoner. Embedding dimension of polyhedral losses. In Conference on Learning Theory, pages 1558-1585. PMLR, 2020.
Jessie Finocchiaro, Rafael Frongillo, and Bo Waggoner. Unifying lower bounds on prediction dimension of consistent convex surrogates. arXiv preprint arXiv:2102.08216 2021.
Jessie Finocchiaro, Rafael M Frongillo, and Bo Waggoner. embedding framework for the design and analysis of consistent polyhedral surrogates. Journal of Machine Learning Research, 25(63): 1-60, 2024.
Peter M Gruber. Convex and discrete geometry, volume 336. Springer, 2007.
Jean-Baptiste Hiriart-Urruty and Claude Lemaréchal. Fundamentals of convex analysis. Springer Science & Business Media, 2004.
Pascal Massart and Élodie Nédélec. Risk bounds for statistical learning. 2006.
Harish G Ramaswamy and Shivani Agarwal. Convex calibration dimension for multiclass loss matrices. The Journal of Machine Learning Research, 17(1):397-441, 2016.
Harish G Ramaswamy, Balaji Srinivasan Babu, Shivani Agarwal, and Robert C Williamson. On the consistency of output code based learning algorithms for multiclass learning problems. In Conference Learning Theory, pages 885-902. PMLR, 2014.
Tyrrell Rockafellar. Convex analysis, volume 11. Princeton university press, 1997.
Cedric Seger. An investigation of categorical variable encoding techniques in machine learning: binary versus one-hot and feature hashing, 2018.
Ingo Steinwart. How to compare different loss functions and their risks. Constructive Approximation, 26(2):225-288 2007.
Kirill Struminsky, Simon Lacoste-Julien, and Anton Osokin. Quantifying learning guarantees for convex but inconsistent surrogates. Advances in Neural Information Processing Systems, 31, 2018.
Ambuj Tewari and Peter L Bartlett. On the consistency of multiclass classification methods. Journal of Machine Learning Research, 8(5), 2007.
Ioannis Tsochantaridis, Thorsten Joachims, Thomas Hofmann, Yasemin Altun, and Yoram Singer. Large margin methods for structured and interdependent output variables. Journal of machine learning research, 6(9), 2005.
Martin Wainwright, Michael Jordan, et al. Graphical models, exponential families, and variational inference. Foundations and Trends@ in Machine Learning, 1(1-2):1-305, 2008

---

Yexiang Xue, Zhiyuan Li, Stefano Ermon, Carla P Gomes, and Bart Selman. Solving marginal map problems with np oracles and parity constraints. Advances in Neural Information Processing Systems, 29, 2016.
Jiaqian Yu and Matthew B Blaschko. The lovász hinge: A novel convex surrogate for submodular losses. IEEE transactions on pattern analysis and machine intelligence, 42(():7355 748, 2018
Tong Zhang. Statistical analysis of some multi-category large margin classification methods. Journal of Machine Learning Research, 5(Oct): 1251, 2004.
12

---

A Notation tables
Notation
Explanation
E R
Prediction space
y E
Label space
P Ay
Subset of simplex over y
5y
Point mass distribution on y E y Index set
[d] {1, [1,...,d] d}
1s {0, 1]dt s.t. (1s); leies
0-1 Indicator on set S S [d]
CC Rd
Closed convex set Surrogate prediction space Projection onto closed convex Permutations of [d]
ue VER
Proje(u) arg min sec ||u x:/2
T TESH
x:''y=- +R+
Discrete loss
L:R4 x +
Surrogate loss
b: +y
Link function
Ey [(,, Y)]
Expected discrete loss
Ey Lu, Y)
Expected surrogate loss
:: +2 2 {Ø}
Property
r, = {pe (r==((p))
Level set of property
prop L
Property elicited by
1-11 y x x (0.1)
Zero-one loss
mode Ay + 2 {0)
Mode property
Table 1: Table of general notation
Notation
Explanation
P PCB CRd
Polytope
(P)
Vertex Set
E(P)
Edge set of P
P : Ay +
Polytope Embedding
pD = conv (1 (-1,1]
Unit cube
pw conv ((T(W) π Sa)) s.t. e gd
Permutahedron
po = conv (1 0)) π St))
Cross polytope
DG Rd + IR+
Bregman divergence w.r.t G
T Rdd x R
(Dg, bp) Induced Loss
Rdd +
MAP Link
Table 2: Table of polytope and embedding notation
Notation
Explanation
H C
Hallucination region
R C P
Strict calibrated region
Ry: Rn tyy
Intersection link level set and strict cal. region Union of Ry
Ry = Ryyy
O_ C Ay
Low-noise assumption
Th = - (01 + 1 E )}
Scaled vertex set Scaled version of anchored by
Py p(conv ($%)
Table 3: Table of calibration region notation
13

---

B Polytopes, Omitted Proofs, and Results
B.1 Polytopes
Convex Polytope P C R2, or simply polytope, the convex hull of finite number of points U1,..., Un E Rd. An extreme point of convex set A, is a point E A such that u Ay (1 A)z with y, 2 E and À E [0. 1], then y = and/or set of extreme points. A polytope can be expressed by the convex hull of its extreme points, i.c. P conv (vert(P)) [Brondsted, 2012, Theorem 7.2].
u. We shall denote by vert(P) a polytope
We define the dimension of via dim(P) == dim(f (afffull()(() where affhull P) denotes the smallest affine set containing P. A set F [ P is face of P is there exists hyperplane (yy o:) == {u R² (u,z) a} such that F = PNH and P C H such that H (y. a) == {u E E (u.y) S a}. Let (.(P) where E [d 1] denote set of faces of dim of a polytope P. A face dimension zero is called vertex and face of dimension one is called an edge. We define the edge set of polytope P by (PP) = {conv ((1,, vj)) (vi, vty) [ (ver((P)) conv ((1;, 03)) E (P)).. We define the neighbors of vertex by ne(e; P) {o E vert
conv ((V, 6)) E E(P)). We will denote conv ((v, B)) E E(P) by as cv,e and no(u; P) by ne(v) when clear from context.
B.2 Omitted Proofs from 3
Proposition 2. For a given induced loss LG the unique report which minimizes the expected loss is n² == arg min Ry (7.6 Y)] = p(p) such that u² E P. Furthermore, every ú E P is minimizer of Ey LL (u, Y)) for some p E Ay-
Proof. By [Banerjee et al., 2005, Theorem 1J. the minimizer of Ey [Lg (u, Y)] Eyey Pa =
ppp). Thus, by the construction of the polytope embedding, it holds that u" = p(p). Since Bregman divergences are defined with respect to strictly convex functions, u" uniquely minimizes By P (u,Y)) Y)).
Conversely, every à E P is expressible convex combination of vertices; hence, by the definition of p, for some distribution, say Ay, it holds û = k()). Therefore, it holds that â minimizes Ey~pl (u,Y)). Y)..
Theorem 3. For any given pair (I. 3) and fo-1 with embedding dimension d <, 1; it holds that H Uyeyconv (vert(P) \ {ry]) 1) n ba and furthermore H. + Ø.
Proof. Choose a y E V. We abuse notation and write vert(P) \ by == vert(P) \ (ey). Observe all E conv (vert(P) ) O nayy can be expressed convex combination of vertices without needing vertex Uy- The coefficients of said convex combination express a E Ay that is embedded to the point E where Pv = O. Yet, by Proposition 2, said u is an expected minimizer of LG with respect to p. Given the intersection with uiff and by Definition 8, holds that Upeyconv (vert(P) nub S H.
We now shall show that H C Useyconv (vert(P) \ uy) n wif. Fix y E 3 Assume there exists point u & conv (vert Uy) Wuf such that there exists some p E Ay where sp()) u, Py and ebt (u) y. Since (1) y and & conv (vert(P) (gy) O ehfe. - must be the that & conv (vert(P) P) b.y) However, that implies that is strictly in the vertex figure and thus must have weight on the coefficient for y. Thus, forming a contradiction that Py = 0 which implies that H Uyeeyconv (vert(P) (P) v.)) wif.
To show non-emptiness of H. we shall use Helly's Theorem (Rockafellar [1997]. Corollary 21.3.2). W.l.ogg. assign index such that y (vI..... .. Md, Id+1..... ... ......... J. Observe the clements of the set each differ by one element. W.l.o.g, pick the first df + elements of the previous set. ( \ y 1
Observe nt+) y yil = D (yi...., .ai....,,,...... ye41 = (d + 1) > 0. Hence, by Helly's 's theorem and uniqueness of ys weyconv (vert(P) vyy) +
Pick a point u' E Nyeyconv (vert(P) \ my). Since whe is well-defined, x' will be linked to some outcome s/ E y and thus u' E conv (vert(P) \ uyy) ) n wif C H. Yet, u' can be expressed
14

---

convex combination which does not use V/y' since it lies in Nyeyconv (vert(P) \ vy). Thus, by using Proposition 2 and by the definition of Hallucination (Def. 8), we have that H. + Ø.
Lemma 1 (Proposition 1.2.4). [Hiriart- Urruty and Lemaréchal, 2004] If y is an affine transformation of IR" and A C I" is convex, then then the image ((A)) is also convex. In particular, if the set A is convex polytope, the image is also a convex polytope.
Lemma 2. Let DG be a Bregman divergence, ip be any polytope embedding, &b be the MAP link, and L be the loss induced by (Da. s). Assume the target loss is fa-1- If point is in a strict calibrated region such that u E for some y E V, it is necessary that u E conv (fvy) U ne(w))) \ conv (ne(vy)).
Proof. If u Ry and u E P\ (conv (fuy) } U ne(ry)) conv (ne(v,))), then can be expressed as a convex combination which has no weight on the coefficient for By. Hence, there exists a distribution embedded into where y would not be the mode, thus violating the initial claim that u E Rg. M
Lemma 3. Let Da be Bregman divergence, vp be any polytope embedding, to be the MAP link, and b be the loss induced by (Da, Q). For any u E E(w,,,)) E E(P), it holds that 1pp (u)] 1.
Proof. Observe, the two vertices of an edge define the convex hull making up the edge and hence.
by (Gruber [2007]. ,Thoremm 2.3) the two vertices are affinely independent. Therefore, all elements of the edge have unique convex combination which expressed by the convex combinations of the edge's 's vertices. Given the relation of the embedding & and convex combinations of vertices expressing distributions, it holds that (yp -(w] = 1.
Lemma 4. Let Da be bregman divergence, yp be polytope embedding, and T. be the induced loss by (DG, .)). For all y E V, it holds that dim(pp(mode,)) = dim( P) 2 2.
Proof. By the construction of sp, we know that dim(P) 2 2. Fix y E V. By Lemma 3, we know that any edge connected from by and é E ne(ry), the distributions embedded into the half of the line segment closer to uy. y is in the mode. By Lemma 1, we know that (((gnode) is convex set. Thus, the convex hull of the half line segments is part of (p(1)odd) Since each vertex has at least dim( P) neighbors, it holds that dim (im((((1godd)) = (P).
Theorem 4. Let De be a Bregman divergence, ip be any polytope embedding, v be the MAP link, and L be the loss induced by (Da,P). There exists a P C Dy with non-zero Lebesgue measure and (PP) S Ry via (I ()) with respect Eo-1-
Proof. Recall that mode (p) == prop((o- = mode(p). Fix y E E.. For contradiction, assume for any ğ E y where y * ÿ. it holds that B,(,,) n (0(g mode) # Ø for all e > O. By Lemma it holds that conv ([2y} U mey..)) S ((>)mode) where May. == {1 a)u, + aT T E ne(vy)) defined by any a E .5). Furthermore, the elements of Umem.,... conv ((w,) U (m)) have one distribution embedded onto it where is the only valid mode thus, we know that yp(mode;) n Umem. conv (fry) U [m]) = B. Since p(1modde) C P is closed and convex, there must exist some non-negative min distance between *p(7)nddg and Ug which we shall denote by dy. For any E E (0, ). we can define (1,) such that (.,v,) n pp = 2, forming a contradiction.
For each By E vert(P) define a de, and let e' E evertt)( (0, d.,.)..) By the construction of P and the definition of eit there exists a > O such that for all u E B (vy) it holds that (u( = y and (vy) C viff For any y Y, we know that Bminfer,e en) (vw)) n P C R, by the construction of our epsilon ball. We claim yp (Bmineeee jere (v)()) n P) is set of distributions for which calibration holds.
For p E Ay such that xp()) E Bminsee e0 (by) n P for some by vert(P), suppose a se- quence {um} converges to pr)
p(p) (equality by Proposition 2). By construction of Bminte.e")) (vy) P, wi (p(p)) y E mode(y) and hence, minimizing report for to (yr p). Furthermore, since Bmin(e',e" (Ny) C u " all elements within Bmin (e((()))) (ry) link to y. Since
} converges to prop[L (1)), there exists some N N and 2 N, such that ||u, (())ll2
15

---

min("',e"), meaning that Ey-pl Dym-pfo-1((/t0 (um))) 1,), Y]] - min Ey~plou-1(1) Y)]. Hence, for any By vert(P), (prop(L0), (i is co-l-raaibrated property with respect to x (Binff (vy) (PP.. Furthermore, by the construction of Bmine e'."" (en) for each By vert(P), have that L is strictly for prop[4ş). Thus, by Theorem 1, (Lg 4/9) is -oal-calibrated for at least the distributions P = EveeeeetP)) (Bmitter ,e") (vy) n P) as well as x(P) S Ry. Furthermore, since Bmiufe for each My E vert(P) is non-empty, we have that P + 2.
B.3 Omitted Proof's from $
Corollary 7. Let yp be an embedding from 2 outcomes into the vertices of p in d-dimensions and define an induced loss Lgg Fix a E [0) and define Oa. (Lg sp :0) ) is fo-1-calibrated for Qa.
Proof. W.l.o.g, say the outcome y1 y is embedded into 4a E vert(PD)). Say .5. Observe that
:
0
0
and that 2 (1 a) a for any a E .5). Hence, for any (0, .5) it holds that P conv ((0, 1)d)) and furthermore pn 0.5 By By symmetry pn and the linearity of for any a E 50. and V, we have that Py is a strict subset of the orthant that contains Vyg Hence, for all y. E y such that * ÿ. it holds that Py n pd = Ø. Thus by Theorem 6, (IG, y a) is lo- 1--f----llll caalibrated for e, where a E (0..5).
Corollary 8. Let yp be an embedding from d' outcomes into the vertices pw in d dimensions
such that w = (0, Fdl ...... lo-1-calibrated over O..
2 d-1) E Rd where 3 d-1 Fix a E [0, 4). Then (L of a) is 2.
36
Proof. Let Aa == conv (f1, E Rd i [d}} and observe p As since for all n, || w/l1 ||ll| = 1. Observe that Pd can be symmetrically partitioned into d! regions with disjoint interiors, one for each permutation E Sa via A7 == (u Aa un < ... S [a]. Fix æ Sa and w.l.o.g assume is associated with the constraints A = {u A
S... ua} implying that
(w:) Ad 9d:.... ... Ad Let
0
d-1)
and define O... With respect to θ,, lety (-'(((()) e y
and ý : i - - (w)) E y such that A E Sa. Thus the set Vy == {(1 2 + (2)6g E )) mapped via jo the following points
((V)) = ((1 1 (T(w)) + ())(()) | =
within the permutahedron.
We shall show that Pa Ag. If this were not true, there would exists element of w E (P())) such such that for some pair of adjacent indices, say i, + [d - 1), w T.
> w iir
For sake of
contradiction, fix E [d 1] and assume there exists f Sq such that w."" w w Observe that
* R.
16

---

any element of (w) can be expressed by 1 using some j E (..,..... d - 1}. Thus,
n.
4+1
{ 1-1
+ (1- (7 3d ( (f(w));
+ (1
3d
(1 2) ( --1
1
2
) 2) 3d
2 3
3d
3d
3d
(i 1) - 1
7) + +
> i(l " + 7(2)
Multiply by 3d
= 1- --d>
for some j.j E {0, 1,...,,dd }} where j + H..
Case 1: (j j): The smallest value possible for 3 - is 0 (d- 1) however, - d > 1 d.
Case 2: > i): The smallest value possible for j - is however, 1 d
Hence, Pg C Aj and specifically, there can exists an extreme point of Pa that lies on the boundary
of AJ as shown in Case 1. However, if a E (0, 4), every extreme point of Py moves closer to T (wr) (besides the extreme point itself already on (w)) and therefore Py lies strictly within AT. By symmetry of p and the linearity of so this would imply that for all y y" E y such that y * y
it holds that PE n Py" =. Thus by Corollary 6, (L """"", (a) is 1o-1-calibrate for O₂, where (0, ).
B.4 Omitted Proofs from $
Lemma 9. Say we are given a cross-polytope embedding Aaa + p and induced loss LG Let (Va, Vb.). ) be the ith diagonal pair (i.e. :p(du.) Va.). Define the property I Aad B element-wit wise by
<, as ag,bss) bz) as, bi) as ba)
if Pa. pb. Pf. Pb,
rp(p);
if Pa. = Pb.
Furthermore define the link Po : IRd + with respect to each diagonal pair as
aig bi)
if u Va. 1|2 lu Ub.
vbuu; Vais Vb. 1.tt :
Oj: bi)
if - Va. 122
u Ub.
Og. bi)
Then ( r*) elicits pr.
Proof. W.l.ogg, fix a diagonal pair (Va, 16) and let v. := 1 and is = -1, Define the embedding to accordingly. We will show that the following is true for all distributions mapped via io pa
|/u Vall > |/u vbll2
+ < pb
OR |u V.a. l2 < ||u 2bll2
< Pa Pb
OR [u Val 12 = |/u Vbll2
< pb-
First, fix p E Azd- Recall, by Proposition 2, the minimizing report for I in expectation is (p)) P c Rd, We will prove the forward direction of the first and second lines. Then the reverse directions follow from the contrapositives.
17

---

Case 1, = Assume for contradiction that Pa and 1kx(p) - v/ 12l2 < (1((p) 18l22. Then
(p(p) - 11, - 11) <(p(p) + 11, (p()) + 11)
(m) - - Σ u <(11 + 1)2 Σ u
U1 1
Sa}) and the orthogonal relation between vertices, to express u E ps as convex combination of vertices, each diagonal pair of vertices coefficients solely influence the position along single unit basis vector. Hence, due to the definition of so, we have M1 = 11 Pa - 1 Pb < 0 since we have assumed that Pa < Pb- Hence -11 < 01 < a contradiction.
By the definition of d-cross polytope p == conv (
Case 2, + Assume p. ps and 11ş(p) l22 llp(p) vbl12. By symmetry with case 1, all the inequalities are reversed, leading to the contradiction that - -1 ut > O.
Case 3: (Pa = -p)): Follows from the and only ifs of cases and
Hence (I.g, (1p) elicits N4.
Theorem 10. Let d 2 2. The mode is (2d, d, mo-Polytope Elicitable for some m E [2d d(2ddd
Proof. We will elicit the mode via the intermediate properties, 1 defined in Lemma First we construct a set of embeddings so that we guarantee that all the soys allow comparison between any pair of outcome probabilities. For example, for each unique pair (a, (), E (2) define embedding: (5,) 1 and (6%) = 1 and embed every other remaining report y {a, b} arbitrarily. Since (L 2b pD) elicits Iv, minimizing each LØ with a separate model yields us comparisons
via the link 16 pt To find the r y such that pr is maximum, we use sorting algorithm that uses pairwise comparisons, such as bubble sort. Hence with Y as Algorithm 1, we have that T(LLE) (D }) mode(p).
Assuming there exist p,s such that there is no redundancy in comparison pairs between each PPs, we would need only 4(2d-1) 2d 1 problem instances. Hence, we establish our lower bound on the needed number of problem instances.
C Hamming Loss Hallucination Example
Hamming loss é : y x y + R4 is defined by Ely. 9) = Σ 1 1, where = 1-1,1,
Suppose d = 3 and we have the following indexing over outcomes
y = (v1 = (1,1,1), = (1, (1, (1,,1,1),3 = (-1,1,,),
ys (-1, (4-
(-1,,,1,,1
Let us define the following distribution
1 Pt = (0, - -
- 6, 3
- 0,
such that >
Ey (311 Y)] = 1 + 6e
Ey [e(2 Y)] = Ey [l(ys, Y)] = Ey [1 Y)] = + 2e
Ey [[,,, Y)] Ey [1(66. Y)] Eyap, [2(y7, Y)] 3 de
Ey-p. [[(s, Y)] = G
For all e [0, 1. the minimizing report in expectation is y1 (1, 1,11. However, Pc, = 0 and thus, a hallucination would occur under calibrated surrogate and link pair.
18

---

D Linking under Multiple Problem Instances
As stated in 5, when using real data, given that these are asymptotic results, we may have conflicting logic for the provided individual reports. In this section, we provide an approach such that the algorithm still reports information the aforementioned scenario and will reduce Algorithm asymptotically. We build a binary relation table M E {0, 1 with the provided reports. Based on M, we select a largest subset of C y/ such that when M restricted to rows and columns corresponding to the elements of S, denoted by Ms. we have that Ms is reflexive, antisymmetrie, transitive, and strongly connected implying Ms has a total-order relation defined over its elements. Having total-order relation infers the mode can be found via comparisons. The algorithm returns (R, S), where is the mode set with respect to the clements of S.
Algorithm 2 Elicit mode via comparisons and the d-Cross Polytopes over well-defined partial orderings
Require: M = ((4,, 2/ )3mm
Learn model hy X' - I2 for each instance (L of E M
For some fixed x E X, collect all Bj + wr (hy(r)) where B3 E Bj Build M E {0, 1)"X* binary relation table with provided {B,}}= as such
Label rows top to bottom by f/...... Vr, and columns left to right by yi..... Vn.
For all (sPPy: By. Py; Pms set Mii, 1 and 0 otherwise.
Select largest subset S y such that Mg is reflexive, antisymmetric, transitive, and strongly connected.
Report (R, + FndMaaxIlemmnttood-55MMM.))
19

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility. transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and precede the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] providedd proper justification is given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
"[No] or "[NA]" is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Any claimed result in the abstract is proved within this work.
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 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, our paper discuss how these results asymptotic.
20

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are 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 on 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, authors should discuss possible limitations of their approach to address problems of privacy and faireess
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 of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Yes. we thoroughly introduce every necessary definition and past result necessary to understand the assumptions that hold under our results.
Guidelines:
The answer NA means that the paper does 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 if they appear in the supplemental material, the authors are encouraged to provide a 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 it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: The results of this work have rigorous proofs presented next to the results or referenced clearly in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
21

---

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. w
For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS 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) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be 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 describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to 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?
Answer: [NA]
Justification: This paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurIPS code and data submission guidelines (https://nips...
public/ guides/ Suddmu ss ssionPolicy) for more details.
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 (ht (https: / //nips.... cc http/publicc/ ////ggiisssseee Code Submi as i ionnollii icy) for more details.
The authors should provide instructions on data access and preparation, including how to 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. 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).
22

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
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?
Question:
Answer: [NA]
Justification: The paper does not include experiments
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core 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, supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the 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, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors 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 out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables 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:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
23

---

The paper should provide the amount of compute required for each of the individual experimental runs as 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 Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /neurips.... cc/public/Ethiissuiiiee
Answer: [Yes]
Justification: None of our conducted work for this paper violates the code of ethics presented.
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 circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: In the body of paper, we provide broader impace section.
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 why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to 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 being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: The answer NA means that the paper poses no such risks.
Guidelines:
The answer NA means that the paper poses 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 not 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: [NA]
Justification: The paper does not use existing assets.
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 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 (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, papersw thcode. com da t sets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/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 obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an 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: The paper does not involve crowdsoureing nor research with human subjects.
25

---

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.
15. 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
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 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 the institution conducting the review.
26


Reviews:
[{"review_id": "Wz4FkCteG8", "reviewer": "Reviewer_vfJE", "summary": "In this paper, the problem of constructing consistent multiclass surrogate losses for the 0-1 loss while reducing the dimension of the scoring function is studied. The concept of partial consistency, which can be dated back to the study of multiclass SVM, is used as a crucial part of this work. It is first revealed that any losses with scoring function’s dimension less than #class number-1 will lead to severe misclassification. Then low noise assumption is used to enable the trade off between (partial) consistency and the scoring function’s dimension number. An attempt of recovering full consistency with several scoring functions of lower dimensions is also made.", "questions": "Please see the weaknesses.", "limitations": "Please see the weaknesses.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. A clear trade off between the strictness of low-noise assumption and scoring function’s dimension number is quantified.\n\n2. The analysis of hallucinations is also enlightening, which provides an interesting insight of why some well-suited models (with some losses) can make wrong predictions even with no real-world evidence.\n\n3. The clear presentation and layout of the results make them easy for readers to understand.", "weaknesses": "While the dimension of predictor is reduced and thus the computational cost of training can be promisingly reduced, the computational cost of the inference stage may increase compared with that of the traditional #class number-dimensional scoring functions. Is there any remedy for this problem?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "The cost of inference can be broken down into two parts: (a) the cost of a forward pass through a model, and (b) the cost of computing the link function. For (a), this is typically unchanged or even reduced by loss function design (reduced when prediction dimension is lowered). For (b), in the paper Structured Prediction with Projection Oracles by Mathieu Blondel, Blondel argues this is relatively cheap since the MAP link projects onto a convex set. Historically, the consistent loss literature has ignored this question of efficient linking and its connections to prediction dimension, and we agree this should be explored further in future work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "y2wlD9XJMS", "reviewer": "Reviewer_BgPT", "summary": "The paper examines the trade-off between consistency and dimensionality in multi-class classification. It has been known that the lower bound on the dimension for consistent surrogate losses under any distribution is $n - 1$, wheren $n$ is the dimension of the input space. The authors propose the notion of partial consistency, which permits the establishment of surrogate losses at much lower dimensions than the input dimension. This method allows for the consistency of lower-dimensional surrogate losses under a low-noise condition and the construction of dimensionally reduced consistent surrogate losses across multiple problem instances.", "questions": "1. Theorem 5 establishes the existence of an $\\alpha \\in [0, 0.5)$ across distributions where consistency is maintained. Is it possible to determine or estimate the value of $\\alpha$ for a specific surrogate loss to guarantee consistency?\n\n2. The max hinge loss, formulated by Crammer and Singer (2001), is inconsistent when $\\alpha = 0$ and consistent when $\\alpha = 0.5$. Do the findings of this paper potentially include such a result as a particular example?\n\n3. The paper examines the asymptotic guarantees of Bayes consistency. Could some of these results be extended to incorporate non-asymptotic consistency guarantees, such as excess error bounds or H-consistency bounds?\n\n4. The low-noise condition mentioned in Line 228 can be considered as the multi-class version of Massart's noise condition. Is it possible to extend the analysis to encompass the broader Tsybakov noise condition?\n\n5. Could the authors provide further elaboration on how to choose an embedding in practice, based on the theoretical results?\n\n6. The results in the paper apply to multi-class classification. Is there any possibility of generalizing them to other scenarios, such as ranking?\n\n7. The use of $\\mathcal{H}$ to denote the hallucination region in line 164 could lead to confusion, as $\\mathcal{H}$ is commonly associated with the hypothesis set. Is there an alternative notation that could be used to avoid this ambiguity?\n\n8. The notion of partial consistency is mentioned in both the abstract and introduction, yet it is not formally defined in the main text. It seems that partial consistency suggests that surrogate reports may not correspond to a single distribution. A formal definition would likely enhance reader comprehension.\n\n9. The approach of using multiple problem instances and aggregating their outputs is intriguing. However, might this method be vulnerable to data imbalances across different problem instances? I am eager to hear the authors' opinions on this.", "limitations": "The authors have adequately addressed the limitations.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is the first study to explore the control of the trade-off between consistency and dimension in multi-class classification.\n\n2. The paper is well-written and clear, even though it is theoretically dense.", "weaknesses": "1. The paper demonstrates the existence of distributions under which consistency holds for low-dimensional surrogates but does not offer much guidance on how to identify such distributions for a given surrogate loss.\n\n2. The paper restricts its study and analysis to asymptotic guarantees.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We briefly respond to individual questions in order:\n\nQ1: In general, finding the $\\min_{\\alpha \\in [0, \\frac 1 2)} \\alpha$ that (almost*) guarantees consistency is possible through property elicitation, though it is laborious. \n*Working directly with consistency conditions is often much more difficult than elicitation, and while elicitation implies consistency, the converse is not always true, but usually holds as long as the argmin is well-defined. \n\nQ2: This work's analysis is limited to Bregman losses (Definition 6) (therefore excluding hinge loss). Understandably, we would like to generalize our analysis in future work; however, the structure of Bregman losses permits us to choose any convex polytope as the embedding structure, allowing our analysis to be rather general from this perspective.\n\nQ3: This is a great question, which requires some subtleties in the answer: first, because $\\mathcal{H}$-consistency is not equivalent to $\\mathcal{H}$-calibration without distributional assumptions that the Bayes optimal $f^* \\in \\mathcal{H}$ (Steinwart 2007 Section 2, under the name P-minimizability). Our proofs typically work through calibration, and extend under this assumption with $\\mathcal{H}$ is the class of all measurable functions. This assumption is relatively common in the $\\mathcal{H}$-consistency/calibration literature, and would permit some of our results and approaches to generalize in a relatively straightforward manner. However, there might be more intensive, but tighter, tradeoffs to be studied under the $\\mathcal{H}$-consistency regime because of the interaction between assumptions on $\\Pr[X,Y]$ (Bayes optimal in class) and $\\Pr[Y \\mid X = x]$ for all $x$ (calibration tradeoffs). In general, when the Bayes optimality assumption is not satisfied, there is an \\emph{approximation gap} that emerges which merits a different analysis from $\\mathcal{H}$-calibration to $\\mathcal{H}$-consistency, and our results would not immediately generalize.\n\nThe question on non-asymptotic analysis would be an exciting direction for future work. We expect such results could be possible to obtain using techniques such as in e.g. Mao et al. NeurIPS 2023, but bounds would likely vary depending on the specific form of the embedding and the convex function $G$ defining the Bregman divergence.\n\nQ4: We were unaware of the literature on Massart and Tsybakov noise while writing this work. We are thankful for pointing this literature out and look forward to incorporating it into future editions of this paper.\n\nQ5: At large, our two results (Corollary 7 and 8)  provide examples on the tradeoffs of dimensionality and consistency that could be insightful in practice. However, this question does require further exploration relative to different problem domains. \n\nQ6: We explored partial ranking in some of our preliminary work; however, the geometry of the level sets became quite intricate, making us unable to establish a general result. \n\nQ7: Thank you for this insight, we will explore a different option to denote hallucinations. \n\nQ8: Currently, partial consistency is implicit via Definition 2, but this is a good point. We plan to write this out explicitly in the body of the work following Definition 2. \n\nQ9: Since this is an asymptotic result, we didn't address questions about sample complexity guarantees. This would require detailed exploration and model assumptions to answer said question; however, as an initial starting point, we expect that using a boosting model could help reduce the effects of data imbalance within the multiple problem instance approach.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2TGwDzu3yT", "reviewer": "Reviewer_2eE5", "summary": "This paper proposes a method called polytope embedding, which embeds multiclass predictions onto real numbers. The paper studies the properties of this embedding, like hallucination and calibration. Further, with low-noise assumptions, the authors showed more calibration results for their embedding in some cases like embedding into the unit cube.", "questions": "I am wondering what exactly the authors' definition of partial consistency is. How exactly are the methods trading off consistency and dimensionality? If the authors mean consistency by hallucination and calibration, which theorem shows how dimension affects these properties.", "limitations": "N/A", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The topic of this paper on how to design a consistent surrogate loss seems interesting. The results proved in the paper also relate to topics that people care about like hallucination and calibration.", "weaknesses": "Even though each result seems interesting, the structure of this paper is not very clear to me. I am open to different arguments but I think it is hard for readers to understand what the authors are trying to show with this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Currently, the definition of partial consistency is implicit via Definition 2, but we say that a surrogate and link $(L, \\psi)$ are partially consistent if it is calibrated only over some $\\mathcal{P} \\subsetneq \\Delta_{\\mathcal{Y}}$ and not calibrated over $\\Delta_{\\mathcal{Y}}$. We will make this explicit after Definition 2.\n\nAt large, we demonstrate tradeoffs for consistency and dimensionality via Theorems 3, 5, and 10. As a negative result, Theorem 3 (Section 3) shows that embedding in d<n-1 dimensions guarantees inconsistency through hallucination, which is a stronger notion than inconsistency. This implies that we cannot have both low dimensionality and full consistency simultaneously, so we move forward in two directions: characterizing partial consistency in low dimensions (Theorem 5; Section 4) and recovering full consistency via multiple (low-dimensional) problem instances (Theorem 10; Section 5).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ckrrx0HGho", "reviewer": "Reviewer_zH7s", "summary": "This paper studies surrogate loss design and the trade-off between surrogate consistency and loss dimension. The contributions are three-fold: (1) the characterization of the hallucination region, where the decoded prediction from the surrogate loss minimizer gives a class with no target probability mass, indicating a completely \"irrational\" prediction; (2) the construction of the (\"weakly but reasonably\" inconsistent) calibrated surrogate and link under the low-noise setup; (3) the decomposition of property eliciation into multiple elicitation problems with low dimensions.", "questions": "Here are the major questions.\n+ In the proof sketch of Theorem 3, it is not very straightforward to see $\\\\mathrm{conv}(\\\\mathrm{vert}(P\\_{-y})) \\\\cap \\\\psi\\_y^\\\\varphi \\\\ne \\\\varnothing$. This is important to ensure that $\\\\mathcal{H} \\\\ne \\\\varnothing$ (before invoking Helly's theorem). Even if this is merely a sketch, it is better to discuss it in my opinion.\n+ Figure 1 (especially the left one) is challenging to understand. Although I can guess that each vertex of the rectangle corresponds to $v\\_y$, I cannot see what each area \"ad\", \"cd\", etc. mean exactly. Either the figure or caption should be refined. Figure 1R (and its caption) is slightly more digestible.\n+ In Theorem 5, the constructed link contains the \"point-set\" distance $\\\\|u - P\\_\\\\alpha^y\\\\|\\_2$. What does it mean exactly? It appears several times afterward (for example, in Theorem 6). I guess we can recover the statements without significant modifications if we modify the link definition slightly.\n\n----\nSome minor points:\n\n- In the last paragraph of the introduction, it is a bit too sudden to talk about the mode for unfamiliar readers. You may say a few words about the relationship between the mode and multiclass classification.\n- In Definition 1, the very general report space is introduced, which I'm not sure is really necessary or not. Subsequently, the discussion is only based on the case $\\\\mathcal{R} = \\\\mathbb{R}^d$.\n  - By the way, the domain of a surrogate loss $L$ should be $\\\\mathcal{R} \\\\times \\\\mathcal{Y}$ in Definition 1, not $\\\\mathcal{Y} \\\\times \\\\mathcal{Y}$.\n- Throughout the paper, \"mode\", \"prop\", and \"vert\" look better with \\\\mathrm, not with \\\\text.\n- In Construction 1, $v\\_y$ is not formally introduced (while I could catch its meaning). In my opinion, this should be formally introduced because it appears repeatedly in the paper.\n- At l.171, \"To show that ...\" does not form a grammatically complete sentence.\n- At l.174, what does it mean by \"the vertex figure\"?\n- At l.194--196, the sentence is not easy to understand mainly because it contains two \"if.\" Could you rephrase it without multiple \"if\"?\n- At l.201, the level set $\\\\psi\\_y$ for the general link is not defined as far as I see, even though the level set for $\\\\psi^\\\\varphi$ is defined in Definition 7.\n- At l.201, $R\\_\\\\mathcal{Y}$ probably matches $R$. Is it true? I'm asking out of curiosity.\n- At l.209, what does it mean by \"a robust sense\"?\n- At l.213, the last \"via $(L,\\\\psi)$ with respect to $\\\\ell_{0-1}$\" is relevant to the definition of the strict calibration region $R\\_\\\\mathcal{Y}$. However, if you append \"via [...]\" in this way directly after $R\\_\\\\mathcal{Y}$, it is a bit hard to understand at first sight.\n- At l.229, $\\\\delta\\_y$ is not defined (though I catch the meaning).\n- At l.233, the notation $\\\\psi\\_\\\\alpha^\\\\varphi$ should be changed if possible because this notation with the subscript/superscript is confusing with the level set notation $\\\\psi\\_y^\\\\varphi$.\n- At l.250, $=$ (in the beginning) should be $\\\\subseteq$ in my understanding.\n- At l.251 and l.267, the link notation $\\\\psi\\_\\\\alpha^P$ should be $\\\\psi\\_\\\\alpha^\\\\varphi$. In regard to this, the notation of $\\\\psi\\_\\\\alpha^{P^\\\\square}$ and $\\\\psi\\_\\\\alpha^{P^w}$ in Section 4.2 are better to be consistent with $\\\\psi\\_\\\\alpha^\\\\varphi$ if possible---the superscript stands for the embedding function, not the embedded space.\n- At l.269, \"$P\\_\\\\alpha^y$ is [...] pairwise disjoint\" should be complemented with \"in $y$\" to be clearer.\n- At l.274, the strict properness is not introduced. Actually, I think the usual calibration suffices in this context.\n- In the appendix, can you make the theorem numbers consistent with those used in the main part? You can do this by using the restatable package.", "limitations": "This work has discussed the limitations. Specifically, there is computational hardness to break down an elicitation problem into multiple low-dimensional problems in Section 5.\n\nThis work does not have potential negative societal impacts because the contributions of this paper are relevant only to general machine learning theory.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "+ **Very well-motivated problem**: Consistent/calibrated surrogate losses, the main topic of this paper, are sometimes too restrictive because the (in)consistency analysis hinges on \"far-fetched\" distributions---as argued by the authors, and as can be seen in some counterexamples to show the inconsistency of the well-known Crammer-Singer hinge loss. If we can remove such \"pathological\" situations from the entire distribution space, we would have a nicer characterization of loss functions. This is the central motivation of this paper.\n+ **Interesting instances to show calibrated surrogates under the low-noise condition**: This paper mainly investigates two situations to convince the benefits of the relaxed notion of calibration: the unit cube and permutahedron. Both make sense with reasonably practical scenarios and provide the first attempt to show the benefits of incorporating the knowledge of the noise level in loss function design.", "weaknesses": "+ **The result with the unit cube may need $d \\\\geq n$**: At first sight, the statement of Corollary 7 (the calibrated link design for the unit cube) does not have any restriction on $\\\\alpha$ (say, any dependency on the embedding $d$), unlike Corollary 8 (the calibrated link design for the permutahedron). When I look at its proof, I suspect we need the condition $d \\\\geq n$ for this because the proof leverages that \"$P\\_\\\\alpha^y$ is a strict subset of the orthant that contains $v\\_y$\" at l.500. Otherwise, it is strange because we can choose an arbitrarily small embedding dimension $d$.\n+ **The trade-off could be seen only for the unit cube case**: The main contribution of this paper is to showcase the trade-off between the consistency and the embedding dimension, as suggested by the title. However, we may not see a clear trade-off in the unit-cube case. This is also related to the above point: Once we have $d \\\\geq n$, there may not be a clear trade-off for $\\\\alpha$ and $d$. Given this, we are not very sure how universally we can observe the trade-off across different elicitation problems.\n\nNevertheless, I don't think these points are significant enough to undermine the contributions of this paper. I expect the authors to address them, which leads to the presentation of the contributions in a more fair/precise manner.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "To clarify Corollary 7, the number of outcomes $n$ is $n=2^d$, and we embed said outcomes into the vertices of the d-dimensional hypercube, which has $2^d$ vertices. It turns out that for this choice of d, we obtain consistency for any value of $\\alpha < 0.5$. In other words, for this choice of $d = \\log n$, there is no dependence on $d$ in the threshold for $\\alpha$ for the hypercube embedding. Although not necessarily a continuous tradeoff, we see this as a positive result since it implies that regardless of the number of outcomes, binary embedding into the unit cube allows for consistency as long as the true outcome has at least half probability.  \n\nRegarding Theorem 3’s sketch, we did not show that $\\mathcal{H} \\neq \\emptyset$; however, in the full proof, we do. We will add this detail to the sketch. For Figure 1, we plan to add clarifying statements for the labels within the captions. With regard to Theorem 5, the point set distance is the minimum distance between said point and any point within the set. We plan to define the point set distance in our work to clarify our result. \n\nConcerning the mentioned minor points, we thank you for your detailed pass through the paper; we plan to incorporate many of your writing suggestions to clarify the presentation of our work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Thank you to all of the reviewers for their feedback. We sincerely appreciate the time and effort you put into these reviews. We see them as very constructive and believe they will help us improve this work. We have written a response for each reviewer addressing individual concerns and questions regarding this work. Once again, thank you for your reviews.

Meta-review: This paper studies consistent multiclass surrogate losses, focusing on the trade-off between consistency and the dimensionality of the scoring function. The reviewers were univocally positive about the submission and therefore I recommend acceptance.
Decision: Accept (poster)