Unifying lower bounds on prediction dimension of convex surrogates
Authors: Jessica Finocchiaro
Rafael Frongillo
Bo Waggoner
Venue: NeurIPS 2021 Poster (2021)
Keywords: Property elicitation
surrogate loss functions
consistency
prediction dimension

Abstract: The convex consistency dimension of a supervised learning task is the lowest prediction dimension $d$ such that there exists a convex surrogate $L : \mathbb{R}^d \times  \mathcal Y \to \mathbb R$ that is consistent for the given task. We present a new tool  based on property elicitation, $d$-flats, for lower-bounding convex consistency dimension. This tool unifies approaches from a variety of domains, including continuous and discrete prediction problems. We use $d$-flats to obtain a new lower bound on the convex consistency dimension of risk measures, resolving an open question due to Frongillo and Kash (NeurIPS 2015). In discrete prediction settings, we show that the $d$-flats approach recovers and even tightens previous lower bounds using feasible subspace dimension.



Unifying Lower Bounds on Prediction Dimension of Consistent Convex Surrogates
Jessie Finocchiaro University of Colorado Boulder jessica. oicchiicccccccciiioooooooooooooo
Rafael Frongillo
University of Colorado Boulder raf@colorado.co edu
Bo Waggoner
University of Colorado Boulder bwag@colorado.c edu
Abstract.
The convex consistency dimension of a supervised learning task is the lowest prediction dimension d such that there exists a convex surrogate L Rd R that is consistent for the given task. We present a new tool based property elicitation, d-flats, for lower-bounding convex consistency dimension. This tool unifies approaches from variety of domains, inchuding contimuus and discrete prediction problems. We use d-flats to obtain new lower bound on the convex consistency dimension of risk measures, resolving an open question due to Frongillo and Kash (NcurIPS 2015). In discrete prediction settings, we show that the d-flats approach recovers and even tightens previous lower bounds using feasible subspace dimension.
Introduction
loss function is called a surrogate when it used to solve a related, but not identical, "target" problem of interest. Selecting hypothesis by minimizing surrogate risk is one of the most widespread techniques in supervised machine learning. There are two main reasons why surrogate loss is necessary: (I) the target problem is to minimize loss, the target loss, that does not satisfy some desiderata such as continuity or convexity; or (II) the target problem is to estimate some largel slatistic and some associated surrogate loss is required to do so, as in many continuous estimation problems. In both settings, a key criteria for choosing surrogate loss consistency, precursor to excess risk bounds and convergence rates. Roughly speaking, consistency means that minimizing surrogate risk corresponds to solving the target problem of interest, i.e. in (I) the target risk is also minimized, the continuous prediction approaches the true conditional statistic.
(II)
Despite the ubiquity of surrogate losses, we lack general frameworks to design and analyze consistent surrogates. This state of affairs is especially dire when one seeks low prediction dimension, the dimension of the surrogate prediction domain. For example, in multiclass classification with n labels, the prediction domain might be IR,, In many type (I) settings, such structured prediction and extreme classification, the prediction dimension of any convex and consistent surrogate often becomes intractably large, forcing one to sacrifice consistency for computational efficiency. To understand whether this sacrifice is necessary, recent work developed tools like the feasible subspace dimension to lower bound the prediction dimension of any consistent convex surrogate [33]. Challenges of type (II) include estimating risk measures such as conditional value at risk (CVaR), with applications in financial regulation, robust engineering design, and algorithmic fairness [1, 14, 35, 42]. Risk measures
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

are not elicitable, meaning they cannot be specified via a target loss, and thus we seck surrogate loss of low (or at least finite) prediction dimension. Recent work [15, 19, 20) gives prediction dimension bounds for some of these risk measures, but without the requirement that the surrogate be convex; bounds for convex surrogates are left as a major open question.
We present a new tool, d-flats, which unifies existing techniques to bound the convex consistency dimension in both settings above. Using this tool, we resolve the above open question for type (II), giving the first prediction dimension bounds for risk measures with respect convex surrogates. We also resolve a similar open question for the mode and modal interval, posed by Dearborn and Frongillo [10]. In settings of type (I), d-flats recover and tighten the feasible subspace dimension result of Ramaswamy and Agarwal [33). Our framework rests on property elicilation, weaker and simpler condition than calibration, as a way to understand consistency across a wide variety of domains.
The "four quadrants" of problem types. Above, discuss significant divergence in previous frameworks: constructing a surrogate given target loss versus a target statistic. In addition to the two possible targets, may have one of two domains: discrete (i.e. finite) target prediction space, like a classification problem, or a continuous one, like a regression point estimation problem. We informally refer to the four resulting cases cases-target loss vs. target statistic, and discrete vs. continuous predictions as the "four quadrants" of supervised learning problems, shown in Table 1. In the context of these quadrants, Figure 1 gives a roadmap of our main results.
Literature on consistency and calibration. We focus on surrogate losses L R I that are consistent, roughly meaning that minimizing L-loss corresponds to solving the target problem of interest.
We give informal definitions of consistency in $ 2.2, with formal definitions in $ A.
When given a target loss E, we roughly define L to be consistent if minimizing L, and applying link function, minimizes é [33, 39, 41, 44). When given instead a target statistic such as the conditional quantile or variance, we introduce notion of consistency in line
Torget loss
Torget statistic
Discrete prediction
Q1, e.g. classification
Q2, e.g. hierarchical classification
Continuous estimation
Q3, e.g. least-squares regression
Q4, e.g. variance estimation
Table 1: The four quadrants of problem types, with an example for each as discussed in & 3.1.
C
Levx
con8evx bounds for
Consistency
Prop.
Q1, Q2. (Cor. 6)
Cor.
Thm.
[3, 40]
Indirect elicitation
d-flats in level sets
Cor. 3
consexx bounds for
Calibration (Q1)
Q3, Q1. (Thm. 3)
Figure 1: Flow and implications of our results. Compared to calibration, suggest indirect elicitation as simpler but almost-as-powerfin necessary condition for consistency. particular, we obtain a testable condition (Theorem 1), based on d-flats, for existence of d-dimennsiona consistent convex surrogate. This condition recovers and strengthens existing calibration- based results for Q1, while simultancously applying to other quadrants. We illustrate the breadth and power of d-flats by resolving two open questions for Q3 and Q4 in $ 4.
2

---

with classical statistics [11, 21, 36). Here we define L to be consistent if minimizing L and applying a link function yields predictions converging to the correct statistic value. The key observation which underpins our approach is that consistency for target losses is a special case of consistency for target statistics (Lemma 1). Therefore, property elicitation which studies the exact minimizers of loss functions allows us to give general lower bounds on prediction dimension of any convex surrogates corresponding to a target task; these bounds apply across all four quadrants. See 2.3 for other prior work on notions of prediction dimension.
As definitions of consistency are difficult to apply directly, the literature often focuses on a weaker condition called calibration, which only applies when given a target loss, e-g. Quadrants and 3. Particularly, several authors [3, 28, 33, 41, 44) show the equivalence of consistency and calibration Quadrant We discuss the additional relationship of elicitation and calibration in & C, and re-derive Proposition 1 via calibration.
Setting
In supervised learning, data is drawn from a distribution D over the space X x ) and the goal to produce hypothesis f - R. Here X the feature space, y the label space, and R the report or prediction space, possibly different from V. For example, in ranking problems, R may be all | permutations over the |Y] labels forming V. We focus on surrogate losses, target problems, and their relationships to conditional distributions p == D2 Pr[Y|X æ] over y given some I E X. We can often abstract away I, working directly with set of (conditional) distributions over outcomes P C Ay, where Ay == {p E R ||pil 1} is the probability simplex over labels. We then write e.g. Exp(r,Y) to mean the expected loss of prediction r E R when Y ~pp
If given, use f: x' R to denote target loss, with predictions r E R. Similarly, L Rd x y + R will typically denote a surrogate loss, with surrogate predictions u E Rd. In this case, d is the prediction dimension of d. We write La for the set of (Borel) B(R+) @ J'measurable and lower semi-continuous surrogates L : Rd x y R such that Ey- Y) < oo for all E Rd . E P, that are minimizable in that arg min,, L,L(u, Y) nonempty for all p E P. (See 5 F.1 for a discussion of this assumption.) Moreover, f C La is the set of convex (in Rd for every y )) losses in La. Set L UdenLa, and Lovx = C A loss f R x y + IR is discrete if R is finite set.
2.1 Property elicitation
Arising from the statistics and economics literature, property elicitation is similar to cal- ibration, but only characterizes exact minimizers of a surrogate [17, 18, 25-27, 30, 37]. Specifically, given statistic or property I of interest, which maps distribution p E P C Ay to the sct of desired or correct predictions, the minimizers of L should preciscly coincide with I. For example, squared loss L(r,y) = (r y)² elicits the mean r(p) Y)
Definition (Property, clicits). A property a set-valued function r : P - 2 (0), which we denote I P = R. A loss L: R x y -> R elicits the property I if
Vp P. r(p)
arg min mig Eu, aE
(1)
The level set of I' at value r E R is is. r- fpe : l'()). We call a property P R discrete if R finite set, as Quadrants 1 and 2. A property single-valued valued if [[p)] = 1 for all E P, in which case we may write I P + R and r(p) E R. As an example, the mean singlo-vaued. We define the range of a property by range r UpEP r(p) S R. When L, we use I = propp/L to denote the unique property elicited by L (for distributions in P) from eq, (1). Typically, we denote the target property by y, and the surrogate by r.
3

---

2.2 Consistency and indirect elicitation
As discussed above, notions of consistency have appeared the literature with respect to target losses, and to target statistics or properties. We give informal definitions of both notions here, with formal versions deferred to A.
Definition 2 (Consistent: loss (informal)). A loss L E and link (L,4) are consistent with respect to larget loss f. if, for all distributions D over X' y and all sequences of measurable lapothesis functions {Im : - R),
(x),) + inf (DL(J(X)))) = EDE(( fm) - inf ing inf(E (X),
Consistency with respoct to property follows similarly, but instead of converging to the optimal target loss, one should approach the optimal (conditional) property value.
Definition 3 (Consistent: property (informal)). Suppose we are given a loss L E C, link function & IRd + R, and properly 7 P 3 R. Moreover, let p. x P + RR be any function satisfying u(r,p) = = > E 7(p)- We say (L, 1)) is consistent with respect to if, there evists a such that, for all D over X x y and sequences of measurable functions {fm X RR),
BoL(fm(X),)) infE
Exp(Ø fm(X), +0.
(2)
Lemma 1 in $ A shows that, in fact, one can capture consistency with respect to a target loss as special case of consistency with respect to a target property. Specifically, given target loss E, one can take = prop [$] and define u(r,p) == Ep)(r,) min, E, Y) to be the é-regret of the report r. This observation allows us to translate consistency from Quadrant 1 to Quadrant 2, and from Quadrant 3 to Quadrant 4; in particular, it will allow us to prove bounds for all four quadrants simultaneously.
As observed in the literature, e.g. [2, 40]. both notions of consistency imply in particular that the link function must map exactly optimal surrogate reports to exactly optimal target reports. In property elicitation, this condition is known as indirect elicitation: for single- valued properties, I' and & indirectly elicit 7 if 7 = o r. The definition below covers the general set-valued case as well.
Definition 4 (Indirect Elicitation). A surrogate loss and link (L, 1) indirectly elicit a property 7 P = R if L elicits property r P = Rd such that for all u E Rd we have T. (.())) We say L indirectly elicits y if such link vp ezists.
Proposition 1. For a surrogate LE L, if the pair (L, is consistent with respect to property 7
or a loss l eliciting 7, then (L, indirectly elicits 7
In other words, indirect elicitation is necessary condition for consistency. In light of Lemma 1, we can use this fact to build prediction dimension lower bounds across all four quadrants.
Implicit in the above elicitation definitions that L minimizable: since I propp [L] is nonempty everywhere, the expected loss L. Y) always achieves a minimum. This restriction is also implicit previous work, e.g., [2]. See & F.1 for further discussion.
2.3 Convex consistency dimension and elicitation complexity
Various works have studied the minimum prediction dimension d needed in order to construct a consistent surrogate loss L: Rd x y + R. typically through proxies such as calibration [2, 33, 40] and property elicitation [15, 18, 20). Motivated by the importance of convex surrogates in machine learning, Ramaswamy and Agarwal [33] introduce the following definition for Quadrant 1; generalize it to all quadrants.
Definition 5 (Convex Consistency Dimension). Given largel loss E: R x R properly 7: P 3 R, its convex consistency dimension consevx(.) is the minimum dimension such that 3L E C and link vp such that (L,v) is consistent with respect to & or 7.

---

In the case of target property Lambert et al. [27] similarly introduce the notion of elicilation complexity. Later generalized by Frongillo and Kash [20), elicitation complexity the lowest prediction dimension of an elicitable property, from some class of properties, from which one can compute 7, We give here the definition for convex-eliciaable properties.
Definition (Convex Elicitation Complexity). Given larget property Y, the convex clicitation complexity elicevx(7) the minimum dimension d such that there is L L2x indirectly eliciting 7.
As consistency implies indirect elicitation, we have the following.
Corollary 1. Given a property P = R or loss e: R x - R eliciting y, we have elicovx (7) S cons conssvx (f).
Finally, related to our work is the embedding dimension of Finocchiaro et al. [12), which is lower bound on both convex elicitation complexity of discrete properties and convex consistency dimension of discrete losses and finite statistics.
3 Lower bounding convex consistency dimension via d-flats
We now turn to the question of bounding the convex consistency dimension for a given task. From Proposition 1, given target property or loss with y propp[[], this task reduces to lower bounding the convex consistency dimension of 7. Theorem 1, crystallized from the proofs of Ramaswamy and Agarwal [33, Theorem 16) and Agarwal and Agarwal [2, Theorem 9), considers a particular distribution and surrogate prediction w E Rd which is optimal for Theorem will show that if d is small, then the level set {p E P E arg min, E,L(u', Y)} must be large; in fact, it must roughly contain high-dimensional flat (of codimension d). By definition of indirect elicitation, there some level set 7r (where u is linked to r) containing this flat as well. We can then leverage the contrapositive of this result: if y has level set intricate enough not contain any digh-dimensional flats, then y cannot have low-dimensional consistent convex surrogate.
Definition 7 (d-flat). For d E N, d-ilat, simply flat, is nonempty set F ker W := (q E P: E,W = Ōō for some measurable W : Rd.
The following lemma yields consistency bounds when combined with Proposition 1. A similar result is found in Agarwal and Agarwal [2, Theorem 9], which bounds the dimension of level sets of a single-valued propp[Z]. Theorem instead bounds the dimension of flats contained in the level sets, an additional power which we leverage in our examples.
Theorem 1. Let T P 3 Ied be (directly) elicited by L E L for some d E N. Let y be either a finite set, or y= R which case we assume each p E P admits a Lebesgue density supported on the sume set for all p E P.1 For all u E raagee and p E Pn, there is some d-flat such that p E F FCF. I..
Proof (finite case). We will prove the result for the case of finite y, and defer the y= R case to $ B. As L is convex and elicits r, we have u E Tpp)) = DE LE,L(u, Y). With y finite, this is additionally equivalent to Ō PLP,0L(U,,) y). where O denotes the Minkowski sum [23, Theorem 4.1.1).2 Expanding, we have ByP,
= {E Pyty I, E aL(u, y) Vy E V}, and thus there W such that Wp = Ey Py Ō where W [ai, vnJ E Rx cf. [33, A th in Thcorem 16). Let Vupp y - Rd + W, be the function encoding the columns of W. Observe that E, Vu
Ö. We take the flat F = kerp Vu,p and have F by construction. To see F C I Tu, from the chain of equivalences above, we have for any q E P
that q E kerp Vu,p = Ö E L(, = E l'))) = q E I...
1 This assumption is largely technical convenience, to ensure that Va. does not depend on p. Any such assumption would suffice, and we suspect even that condition can be relaxed. 20 represents the subdifferential Ōf(x) {z: f(x') f(x) 2 (z,x' x) Vr'}.
5

---

Speech
Figure 2: Hierarchical prediction example with labeling tone of speech. We take R the leaves of this tree, shown blue.
Active
Non-active
Median
Passive
Theorem 1 now allows us to derive bounds on convex consistency dimension by considering distributions and property values that are either single-valued (Corollary 2) or on the relative interior of the simplex with finite y (Corollary 3). Proofs are deferred to $ B.
P = R and d E N be given. Let y be either a finite set, or y= R, in which case we assume each p E P admits a Lebesgue density supported on the same set for all p E P. Let P with [r(p) 1, and take ((p) = {r). If there is no d-flat with p E Tr: then cons.vx(7) 2 elicevx (7) 2 dd+1.
Corollary 2. Let target property
Corollary 3. Let an clicitable target property 7: = given, where P S Dy is defined over finile set of outcomes y, and let d E N. Let p E relint(P). If there is no d-flat F with p E F E Tr, then consevx(7) 2 elicovx (7) 2 d +.
3.1 Illustrating the condition in all four quadrants
We now illustrate how to apply Theorem 1 to construct lower bounds on convex consistency dimension for targets across all four quadrants of Table 1. Throughout the examples, we will have | = so that the probability simplex can be visualized in two dimensions (Figure 3). For each, we take d = 1, and thus ask whether any 1-flat (a line in the figures) passes through the point while staying within the corresponding level set.
Q1: Classification with an abstain option. The abstain target loss is well-studied variation of 0-1 loss that allows for an "abstain" report that gives a lesser punishment 1/2 for abstaining, Ir & [y, + (1/2)1{r = L}. Since we are given a discrete target loss, this problem fits nicely into Quadrant 1.
L 17, 8, 29, 33, 34). Formally, the target loss is (1/2
To apply Theorem 1, we first consider the abstain property y elicited by 21/2, where one predicts the most likely outcome if Pr[Y y] 1/2 and otherwise "abstains" by predicting I. For the depicted distribution E relint(y1). we cannot fit a 1-flat (line) fully contained in Yi that passes through p. By Corollary 3, we can conclude consevx(71/3) 2 when | = 3, meaning there is consistent convex surrogate in 1 dimension. This lower bound matches the upper bound from the convex surrogate of Ramaswamy and Agarwal [33].
Q2: Variation of hierarchical classification. Ramaswany et al. [32] study hierarchical classification tasks, in which labels are arranged in a tree and one wishes to predict the deepest node in tree that is "likely enough" [5, 43). Consider the variation of this task where one can only predict leaves of this tree. For example, Figure 2 depicts a speech classification task where speech is either active non active, and non non-active is further subdivided into median and passive. is natural to predict active if that label more likely than both non-active labels combined, and otherwisc to predict the most likely of median and passive:
acttve Pactive 2 1/2
<())
median Pactive S 1/2 A Pmedian 2 Ppassive
passive Pactive S 1/2 A Ppassive 2 Pmodian
This "T-shaped" property, depicted in Figure 3 (Q2), falls under Quadrant 2, as it is not elicited by any target loss.3 Like abstain, we cannot fit. 1-flat (line) entirely contained in the level set Tpassive through the depicted p, so Corollary 3 gives consevx(7)= 2.
Q3: Least-squares regression Squared loss is commonly used in machine learning and statistics for continuous estimation, making it the canonical choice for Quadrant 3.
"The cells of finite elicitable properties form power diagrams, generalization of Voronoi diagrams, which disallow this "T-shaped" configuration [17, 26).

---

(Q1)
1/2
(Q2)
active
Figure 3: Example properties for each quadrant. Throughout, we take to the distribution = 0..3, 0.4) according to the left, top, and right outcomes respectively. (Q1,Q2) We can- not fit a 1-flat (line) through p without leaving the level sets 7T and Tmoddam: respectively; The- orem 1 implies that there is 1-dimensional consistent con- vex surrogate for cither prob- lem. (Q3) Squared error is a 1-dimensional convex loss, and indeed it elicits the mean of Y, whose level sets are all 1-flats. (Q4) The level sets of the vari- ance are curved and cannot. fit 1-flat; from Theorem there no I-dimensional convex surro- gate consistent for the variance.
T.L
Imeddian
8/1
3/
passive
median
(Q3)
y
(Q4)
y =
y = To.69
y = 1
To.1
Squared loss is a 1-dimensional convex loss which elicits the mean r(p) = EY Theorem 1 therefore states that we can fit 1-flat through any distribution p while staying within the corresponding level set. In fact, the level sets of the mean are all exactly 1-flats, as demonstrated in Figure (Q3).
Q4: Variance Consider the task of estimating the variance Var(p) = - Ey
The variance is not (directly) elicitable as its level sets are not convex [27, 31), meaning this task falls under Quadrant Interestingly, the fact that the variance is not elicitable does not yield lower bound on elicitation complexity of 2, as it does not rule out the variance being a link a real-valued convex-elicitable property; ef. Frongillo and Kash [20, Remark 1]. In F.2, we show elicevx (Var) = 2, meaning the lowest dimension of convex loss to estimate conditional variance is 2. This lower bound will follow from Theorem in $ 4 using the fact that variance the Bayes risk of squared loss. While perhaps intuitively obvious, even this simple result is novel.
3.2 Relation to feasible subspace dimension
In Quadrant 1, Ramaswany and Agarwal [33] give a lower bound on convex consistency dimension roughly by the co-dimension of the subspace of feasible directions Se(p) of convex set C at a given distribution p such that E C, which is loosely the "most full" subspace of C containing a neighborhood around p.
Se(p) {u E R"
3eo such that p + Eu CVe (-eo,
Theorem 1 subsumes the bounds given by Ramaswamy and Agarwal [33] by showing that, if there is a d-flat through p fully contained in level set &r (so we apply Theorem 1) then the subspace of feasible directions at the same p E C == 7, has co-dimension at most d, discussed in detail in D.1.
Proposition 2. Suppose we are given discrete loss R x - IR eliciting the property 7: Ay = R. Fix p E relint(Ay) and take r E R such that p Er. If consevz there crisis a d-flat F C 7r through p. Moreover, F is subspace of feasüble directions over the sel "r intersected with the simplex. Therefore, codim(S.,, (p)) < d, and in lurn, this implies ce dim()) > d codim(S.,. (p)).
d, then
In other words, any d-flat through p is a subspace of feasible directions of co-dimension at most d, so Theorem I provides a weakly tighter lower bound on convex consistency dimension than Ramaswamy and Agarwal [33, Theorem 16. In fact, the d-flats bound can be strictly tighter; in D we show that the abstain example from Figure 3 (Q1) yields d-flats lower

---

bound of 2 and a feasible subspace dimension lower bound of 1. This gap stems from the fact that feasible subspace dimension uses only local information of the property to construct lower bounds, while d-flats in Theorem 1 allow us to additionally use global information. See Figure 4 in & D for an illustration.
Application: Risk Measures, Mode, and Modal Interval
We now turn to two main applications of Theorem 1: new lower bounds on the convex consistency dimension of risk measures ($ 4.1) and the mode and modal interval ($ 4.2). In both cases, we build on previous results due to Frongillo and Kash [19, 20) and Dearborn and Frongillo [10] which showed lower bounds with respect to identifiable properties; a property is d-identifiable if its level sets are all d-flats, as in Figure 3 (Q3). In contrast, properties elicited by convex losses are generally not identifiable, particularly when the loss is non-smooth. For example, the properties elicited by hinge loss and the abstain surrogate are not identifiable, as their level sets are not flats; see Figure 3 (Q1). therefore might appear that entirely new ideas are needed. Indeed, both papers above pose developing similar bounds with respect to convex-elicitable properties as a major open question.
Using our d-flats framework, we resolve both open questions with new lower bounds in both settings. Our framework clarifies the relationship between d-identifiable properties and properties elicited by d-dimensional convex losses: the level sets of the former are d-flats by definition, while the level sets of the latter are unions of d-flats by Theorem 1. careful examination of the arguments of Frongillo and Kash [19, 20] and Dearborn and Frongillo [10] reveals that they largely rely on the containment of d-ilats in level sets, rather than the full structure of identifiable properties. As such, although quite subtle in the case of risk measures, the general structure of these previous proofs go through for convex-eliciaabl properties: since no d-flat could be contained in a particular level set, no union of d-flats could be either. Our lower bounds therefore match both of these papers, though we conjecture that our convex consistency bounds could be tightened in some cases.
4.1 Risk measures (Q4)
The problem of estimating a risk or uncertainty measure of Y is of central importance in financial regulation [1, 6, 14] and robust engineering design [4, 35, 38). Risk measures include the upper confidence bound E[Y) + Varl,] or the conditional value at risk (CVaR) defined below in eq. (3), in either conditional or unconditional contexts. Uncertainty measures include the variance, entropy, or norm of the distribution of Y. Risk and uncertainty measures are typically not elicitable, so this problem falls under Quadrant 4. Frongillo and Kash [19, 20] give prediction dimension lower bounds for broad class of risk and uncertainty measures, namely Bayes risks. As stated above, these bounds are with respect to identifiable properties, and bounds for convex surrogates are left as major open question.
We resolve this open question using our d-flats framework, giving matching result. for convex-elicitable properties (Theorem 2). First recall the definition of the Bayes risk.
Definition 8. Given loss function L: : R x y - IR for some report set R, the Bayes risk of L is defined L(p) == infreR Lr, Y).
Condition 1. For some E rangell I, the level set r, = kerp V is d-flat presented by some V:y y + Rd such that 0 E int (E,V E P}.
Theorem 2. Let P be a convez set of Lebesque densities supported on the same set for all p E P. Let - Rd satisfy Condition I for some r E Rdd Let L Lovx elicit I such that L is non-constant on r,.. Then cons 2 elicevx 2 d
+
To illustrate the theorem, we briefly apply it to one of the most prominent financial risk measures, the conditional value at risk (CVaR). Several other applicat from Frongillo and Kash [19, 20), such as other risk measures, entropy, and norms, follow similarly. The authors observe that CVaR can be expressed as Bayes risk; for 0 < < 1, we may define
CVaR,, (p) = inf Ep (r Y)1
(3)
rek
8

---

which is the Bayes risk of the transformed pinball loss (r, y) = 1 y) r. In turn, La elicits the o-quantile, the quantity qa (p) such that Pry ( 2 4a (p)] = a. Following Frongillo and Kash [20), we will restrict to the set Pa of probability measures over R with connected support and whose CDFs are strictly increasing on their support, so that da is single-valued. Under mild assumptions, we find that there is no consistent real-valued convex surrogate for CVaRa.
Corollary 4. Let P be a conver set of continuous Lebesgue densities on y = R with allp P having support on the same interval. If we have P1, P2, Ps. p2 P with qa (p1) < qa (Pz) < (a(ps) and (P2) # (V)Ra(P)), then consevx (CVaRa)) 2 edicevx(CVaR, 2 2.
As first shown by Fissler et al. [15], the pair (CVaR,,, 9a) is jointly identifiable and elic- itable, but not by any convex loss [13, Prop. 4.2.31]. We conjecture the stronger statement elicevx(C (CVaRa) 2 3, which if true would constitute an interesting gap between elicitation complexity for identifiable and convex-clicitable properties.
4.2 Mode and modal interval (Q4, Q3)
For finite ()), the mode Twode (p) = arg max p(y) is elicited by 0-1 loss. By contrast, for ) = R, the mode is not elicitable [22], landing it in Quadrant 4. Defining the mode is subtle for general distributions; here let us assume p has smooth and bounded Lesbegue density fp. and define the mode the same way, Thood (p) arg max fp(v). Dearborn and Frongillo [10] recently showed a strong impossibility result, that the mode has countably infinite elicitation complexity with respect to identifiable properties. In other words, it is as hard to elicit the mode as the full distribution p itself. Complexity with respect to convex-elicitalee properties is left as an important open question.
We resolve this question, with a matching infinite lower bound for convex-elicitable properties. In light of our d-flats framework, the result is nearly immediate, as the proof Dearborn and Frongillo [10] already showed that the level sets of the mode cannot contain any d-flats.
(countably infinite) with respect to P, the class of probability measures on y = R with smooth and bounded density and such that mmdde singlevvauedd
Theorem 3. The mode has comsevx((imode) clicevx (ffCeex(((mdde) (*moode
Proof. The proof of Dearborn and Frongillo [10, Theorem 1] gives a distribution p E P with (p)de(() = 0 =: u. It then introduces an arbitrary identification function V R x y - R k E N, and value have an arbitrary f-flat containing p. The proof then proceeds to construct some p' E F with "mude # Corollary 3 now gives consevx (Ttuode ellieex((hmode 2 k + 1. As k was arbitrary, the result follows.
R such that p kerp (rr,.). Letting F kerp V(r,-), we therefore
A closcly related property for any 3 > is the (midpoint of the) modal interval of width 23, given by 75(p)= = arg max P([x B, + 3)) Interestingly, unlike the mode for y = R, the modal interval is elicitable, by the target loss Ex(r, = 1(| y > B). The problem of estirattin the modal interval therefore could be thought of as falling under Quadrant 3.
As observed in Dearborn and Frongillo [10, Corollary 1), the properties "mode and Yo coincide with the family of distributions needed in their Theorem 1, meaning the conclusion of Theorem 3 transfers to the modal interval as well.
Corollary 5. For any 3 > 0, the modal interval oo (countably infinite) with respect to P3, the class probability measures on y = IR with a smooth and bounded density, and such that "/mode and "18 are single-valued.
Tt : P3 - R has consevx
(11)) (licevx(77))
Thus, while 7,9 is elicitable, it does not have any consistent finiteddimensional convex surrogate. While this statement may seem counter-intuilive, recall that the mode for finite [}] has consevx (onseex(YYmode) = / - 1. Taking the limit as [ - oo, one may therefore expect an infinite convex consistency dimension for both the mode and modal interval.
9

---

Conclusions and future work
In this work, introduce
tool to generate lower bounds the convex consistency dimension of general prediction tasks. This tool is simultancously broader, stronger, and casier to understand than previous results. Its breadth is demonstrated by applying to multiple problem types simultaneously ($ 3), while its strength is demonstrated by proving new bounds on convex consistency dimensson ($ 4), and ease is apparent when observing that indirect elicitation is a strictly weaker notion than calibration the most common proxy for consistency. We then apply our framework to yield new bounds on convex consistency dimension for entropy, risk measures, the mode, and modal intervals.
Several important questions remain open. Particularly for the discrete settings, would like to know whether one can lift the restriction that surrogates always achieve a minimum; we conjecture positively (sce $ F.1). The observation that bounds are tight calibration- based bounds, yet we use the weaker condition of indirect clicitation, motivates the study of how much weaker indirect elicitation is than calibration. More broadly, we would like to characterize consevx and elicavx and develop a general framework for constructing surrogates achieving the best possible prediction dimenssion.
Acknowledgments and Disclosure of Funding
We thank Adam Bloniarz and Nishant Mchta for several key suggestions and insights. This material is based upon work supported by the National Science Foundation under Grant No. 104-2045347 and Graduate Research Fellowship No. DGE-1650115.
References
[1] Carlo Acerbi and Balazs Szekely. Back-testing expected shortfall. Risk, November 2014.
[2] Arpit Agarwal and Shivani Agarwal. On consistent surrogate risk minimization and property elicitation. In JMLR Workshop and Conference Proceedings, volume 40, pages 1-19, 2013. URL http: /ttp://www. jww. wwtp:ioll/poooeeee///ooo
org/ pproceddangg/ppperr////////
pdf.
3 Peter Bartlett, Michael I. Jordan, and Jon D. McAuliffe. Couvexity, classification, and risk bounds. Journal of the American Statistical Association, 101 156, 2006. URL http://amster. tandf onl one.in..iinno..oommoooom.eeeeeee com attoi//ass///// http:////.11.1111101116661115001 http://.......100001160000000000
[4) Hans- Beyer and Bernhard Sendhoff. Robust optimizationn:inoomommoooo comprehensive survey. Computer methods in applied mechanics and engineering, 196(33):3190 3218, 2007. URL http://www.ccennnddreeee.. wttpe/eeeeccccccccceeeeeeeeeo www.sciinne/aaaaicccciccicceeeee
5) Felix Burkhardt, Astrid Paeschke, Miriam Rolfes, Walter F Sendlmeier, and Benjamin Weiss. A database of german emotional speech. In Ninth European Conference on Speech Communication and Technology, 2005.
66 Sean D. Campbell. A review of backlesting and backlesting procedures. Divisions of Research & Statistics and Monetary Affairs, Federal Reserve Board, 2005. URL httpep/ssseereeeeeooooo//ss////p
pdf. [7] Chi- Chi-Kenng Chow. An optimum character recognition system using decision functions. IRE Transactions on Electronic Computers, (4):247-254, 1957.
www.rrrrreeeeeeeeeeeeeeeeeeeeeee http://www.eetrrarreeeeee
http:///ww.
8 Corinna Cortes, Giulia DeSalvo, and Mehryar Mohri. Learning with rejection. In International Conference on Algorithmic Learning Theory, pages 67-82. Springer, 2016.
99 Koby Crammer and Yoram Singer. On the algorithmic implementation of multiclass kernel-based vector machines. Journal of machine learning research, ((Dec):264) 265-292, 2001.
[10] Krisztina Dearborn and Rafael Frongillo. On the indirect elicitability of the mode and modal interval. Annals of the Institute of Statistical Mathematics, 72(5): 1108, 2020.
[11] Jianoing Fan and Qiwei Yao. Efficient estimation of conditional variance functions in stochastic regression. Biometrika, 85(3):645 660, 09 1998. ISSN 0006-3444. doi: biomet/85 10. 10.1093/ ww..19999ott/////ee /85.et./8...666 645. URL https: /doi. 00g/10.110 10t.0///e////////55555/ 3.665....5
10

---

[12] Jessic Finocchiaro, Rafael Frongillo, and Bo Waggoner. Embedding dimension of polyhedral losses. The Conference on Learning Theory, 2020.
[13] Tobias Fissler. On higher order elicitabilily and some limit theorems on the Poisson and Wiener space. PhD thesis, 2017.
[14] Tobias Fissler, Johanna Fasciati- Ziegel, and Tilmann Gneiting, Expected Shortfall is jointly elicitable with Value at Risk-Implicn Implicaaiisss for backtesting. Risk Magazine, 2016.
[15] Tobias Fissler, Johanna F Ziegel, and others. Higher order elicitability and Osband's principle. The Annals of Statistics, 44(4):160-11707, 2016.
[16] Gerald B Folland. Real analysis: modern techniques and their applications, volume 40. John Wiley & Sons, 1999.
[17] Rafacl Frongillo and Ian Kash. General truthfulness characterizations via convex analysis. In Web and Internel Economics, pages 354 370. Springer, 2014.
[18] Rafael Frongillo and lan Kash. Vector- Property Elicitation. In Proceedings of the 28th Conference on Learning Theory, pages 1-18, 2015.
[19] Rafael Frongillo and Ian A. Kash. On Elicitation Complexity. In Advances in Neural Information Processing Systems 29, 2015.
[20] Rafael Frongillo and Ian A Kash. Elicitation Complexity of Statistical Properties. Biometrika, 11 2020. ISSN 0006-3444. doi: 10.1093/ /aa////oomt//saaae asaa093. URL https:
//doi.org/11 10.oo////.... 100.///ommt///aa055...
[21] László Györfi, Michael Kohler, Adam Krzyzak, and Harro Walk. A distribution-free theory of nonpurametrri regression. Springer Science & Business Media, 2006.
[22] C. Heinrich. The mode functional is not elicitable. Biometrika, page ast 2013. URL http://biomet. wat.o/metoofffdoourrro..oo oxfordjournals wrrg//ontenntearl//21133//// biomet ast048. short.
[23] Jean- Baptise Hiriart- Urrutyy and Claude Lemaréchal. Fundamentals of conver analysis. Springer Science & Business Media, 2012.
[24] Aleksandr Davidovich Ioffe and Vladimir Mikhailovich Tikhomirov. On minimization of integral functionals. Functional Analysis and Its Applications, 3(3):218 227, 1969.
[25] Nicolas S. Lambert Elicitation and evaluation of statistical forecasts. 2018. URL betps://welt stanford. www.oord..d..deeeeeeeeeeeeeeeeee http:///eeerr/ppppes//llttttaaaa .dff.
[26] Nicolas S. Lambert and Yoav Shoham. Eliciting truthful answers to multiple-choice questions. In Proceedings of the 10th ACM conference on Electronic commerce, pages 109-118, 2009.
[27] Nicolas S. Lambert, David M. Pennock, and Yoav Shoham. Eliciting properties of probability distributions. In Proceedings of the 9th ACM Conference on Electronic Commerce, pages 129-138, 2008.
[28] Yi Lin. A note on margin-based loss functions in classification. Statistics & probability letters, 68(1):73 82, 2004.
[29 David Madras, Toniann Pitassi, and Richard Zemel. Predict responsibly: improving lairness and accuracy by learning to defer. In Proceedings of the 32nd International Conference on Newral Information Processing Systems, pages 6160, 2018
[30] Kent Osband and Stefan Reichelstein. Informatioon compensation schemes. Journal of Public Economics, 27(1):107-115, June 1985. ISSN 0047-2727. doi: 1016/ 0047-2727 pi1/004727278590313..
URL http:/ /twt://www.... sciencedirect.c com cwwm/sciiin///rricceeee.
[31] Kent Harold Osband. Providing Incentives for Better Cost Forecasting. University of California, Berkeley, 1985.
[32] Harish Ramaswamy, Ambuj Tewari, and Shivani Agarwal. Convex calibrated surrogates for hierarchical classification. In International Conference on Muchine Learning, pages
1552-1860) 2015.
[33] Harish G Ramaswamy and Shivani Agarwal. Convex calibration dimension for multiclass loss matrices. The Journal of Machine Learning Research, 17(1):397-444 2016.
11

---

[34] Harish G Ramaswany, Ambuj Tewari, Shivani Agarwal, et al. Consistent algorithms for multiclass classification with an abstain option. Electronic Journal of Statislics, 12 2018.
[35] R. Tyrrell Rockafellar and Johannes O. Royset. On buffered failure probability
in design and optimization of structures. Reliability Engineering & System Safety,
95(5):499-511) 510, 2010. URL http: /wwp:://wwwww...o http:://wwwssceeeeeee sciencedirect.comm $0951832010000177.
[36] David Ruppert, M. P. Wand, Ulla Holst, and Ola Hösjer. Local polynomial variance- function estimation. Technometrics, (9(3):262227: 1997. doi: 10. (0.1000/00400100..1
10485117. URL https: bttps::/wwww.e www.:w:aandooooon..m.cm cttm//bblaaaa/110000000000000000 1997. 10485117.
[37] L.J. Savage. Elicitation of personal probabilities and expectations. Journal of the American Statistical Association, pages 783 1001, 1971.
[38] Muhammad Shahbaz, Zhong-Hus Han, W. P. Song, and M. Nadeem Aizud. Surrogate- based robust design optimization of airfoil using inexpensive Monte Carlo method. In Applicd Sciences and Technology (IBCAST), 2016 19th International Bhurban Confer- ence on, pages 197 504. IEEE, 2016. URL http::/iieeepi:: dbcument/7429924//
ieee org/abstract/
[39] Ingo Steinwart. How to compare different loss functions and their risks. Constructive Approzimation, 26(2):222-22) 2007.
[40] Ingo Steinwart and Andreas Christmann. Support Vector Machines. Springer Sci- ence & Business Media, September 2008. ISBN 978-0-387-77242-4. Google-Bood Books-ID: HUnqnrpYt4IC.
[41] Ambuj Tewari and Peter L. Bartlett. On the consistency of multiclass classification methods. The Journal of Machine Learning Research, 8:1007-1025, 2007. URL http: //dl. waameoog///ctttii htte://ttattoonn.cnt111113333
[42] Robert Williamson and Aditya Menon. Fairness risk measures. Conference on Machine Learning, pages 6786 6797. PMLR, 2019.
In International
[33 Zhongzhe Xiao, Emmanuel Dellandrea, Weibei Dou, and Liming Chen. Hierarchical classification of emotional speech. IEEE Trunsactions on Multimedlia, 37, 2007.
[44] Tong Zhang. Statistical behavior and consistency of classification methods based on convex risk minimization. Annals of Statistics, pages 56 36-85, 2004.
12


Reviews:
[{"review_id": "hriczxVWcSU", "reviewer": "Reviewer_5yYm", "summary": "This paper introduces the notion of d-flats for lower bounding the convex elicitation complexity of a property, which also lower bounds the convex consistency dimension of the property. These quantities are studied in the design and analysis of loss functions to accomplish prediction tasks. \n\nThe authors use d-flats to establish lower bounds on the convex elicitation complexity of a variety of properties, such as classification with an abstain option, variance, CVaR, mode, and modal interval. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is exposited clearly and has a clear narrative: the proposed method of lower bounding convex consistency dimension by using d-flats to lower bound a smaller quantity, convex elicitation complexity, is a useful technique which unifies previous results and provides lower bounds for some properties which were not previously known. The technique itself appears natural and elegant, derived by writing the subgradient condition for optimality and deducing from it using elementary properties that there exists a subspace in the probability set of codimension at most d. The approach demonstrates novelty, as the most prominent previous approach for lower bounding convex consistency dimension was the feasible subspace dimension approach provided by Ramaswamy and Agarwal [33], which the authors show is weaker than the method of d-flats (the d-flat result derives the feasible subspace result in the appendix). Furthermore, the new lower bounds on the complexities of classification with an abstain option, variance, CVaR, mode, and modal interval also demonstrate the novelty.\n\nA question that I have is whether the method of d-flats can be applied to the multiclass version of the classification with abstain option problem; can a corresponding lower bound be proved without drawing the level sets and visually observing that no lines through a point fit in the level set.\n\nAnother question is, what is the significance of lower bounding the prediction dimension of a property? Does this have any bearing on how people normally predict properties in practice? Unless stated otherwise, it feels like most of the time, people know what loss function to use to obtain a property, and the lower bound isn't necessarily adding anything to the practice. \n\n(minor typo in line 83, \"prediction dimension of d\")", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "RmR7tzeE-nH", "reviewer": "Reviewer_kpyj", "summary": "This paper looks at convex surrogates of supervised loss functions and tries to obtain lower bounds for the convex consistency dimension which is the lowest prediction dimension with a consistent convex surrogate. They look at two variants of the problem, namely target loss and target statistic and separately for discrete and continuous cases. They define a tool called d-flat which can be used to bound the convex consistency dimension. The work largely relies on the condition of property elicitation, which is a weaker condition than calibration and is defined on a variety of domains such that the convex elicitation complexity lower bounds the convex consistency dimension. They also use the idea to find solutions to two open problems, one related to lower bounds of risk measures and the other for mode and modal interval.", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper looks at convex surrogates of supervised loss functions and tries to obtain lower bounds for the convex consistency dimension which is the lowest prediction dimension with a consistent convex surrogate. They look at two variants of the problem, namely target loss and target statistic and separately for discrete and continuous cases. They define a tool called d-flat which can be used to bound the convex consistency dimension. The work largely relies on the condition of property elicitation, which is a weaker condition than calibration and is defined on a variety of domains such that the convex elicitation complexity lower bounds the convex consistency dimension. They also use the idea to find solutions to two open problems, one related to lower bounds of risk measures and the other for mode and modal interval.\n\nThe paper has a lot of involved concepts, particularly for a reader not familiar with the area, but the authors provide enough context and links to related work to form a broad idea of the general principle of both convex consistency dimension and the idea of d-flats/property elicitation. I am also curious whether understanding about the lower bound of the convex consistency dimension necessarily means attainability (the lower bound always is reached for some convex surrogate) and also whether it would be possible to estimate such a surrogate given the understanding of the prediction dimension. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 "}, "extra_text": {}}, {"review_id": "DxYs6MjHGYL", "reviewer": "Reviewer_K35K", "summary": "The authors introduced a new tool for proving lower bounds on the convex consistency dimension, which is defined as the smallest dimension d such that there exists a link function and convex loss function L of dimension d that are consistent. They showed a connection between the convex consistency dimension and the existence of d-flat. The result can be applied to a wide range of tasks, such as classification, regression and variance estimation. In particular, they apply the tool on risk measure (4.1) and mode and modal interval (4.2) and obtain new lower bounds in these settings.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Questions:\n1.What are the practical implications of this result? Will the theory here provide guidance on how to select a surrogate loss function?\n2.The paper never defined consistency in the main text despite using the term frequently. I would suggest moving Definition 7 and 8 to the main text.\n\nI apologize that I have no expertise in this area and don’t know anything about the relevant literature, and therefore my confidence is low. The paper seems to provide a nice tool for proving convex consistency dimension lower bound. Though I don’t know about the impact and significance of the result in the area. Therefore I will vote weak accept for now.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "2a3jO56ADWT", "reviewer": "Reviewer_GhRx", "summary": "This paper presents a new tool to generate lower bounds on the convex consistency dimension of continuous and discrete prediction tasks. The authors apply this tool, called $d$-flats, to yield new bounds on convex consistency dimension for risk measures, mode and modal interval. They show that d-flats recover and tighten the feasible subspace dimension result in discrete prediction settings.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The new tool used in this paper is based on property elicitation, which is a widely studied area in statistics and economics. Compared with calibration, indirect elicitation is a weaker and simpler condition for consistency. It’s interesting that newer bounds obtained based on indirect elicitation are as tight as calibration-based bounds. \n\nThe authors give the first prediction dimension bounds for risk measures with respect to convex surrogates via d-flats. \n\nThe authors refer to the four cases–target loss vs. target statistic, and discrete vs. continuous predictions–as the “four quadrans” of supervised learning problems. Using property elicitation, they are able to yield lower bounds on prediction dimension of any convex surrogates. Moreover, these bounds apply across all four quadrants.\n\nThis is a well written paper and I recommend its acceptance. The theory in this paper will be helpful to understand how to construct consistent convex surrogates for target losses or properties. \n\nI have some (minor) comments listed below.\n\n1.\tThis paper considers examples like classification and regression problems, I was wondering if d-flats could be used to study the subset ranking losses.\n2.\tIn the first two paragraphs of the “Setting” section, some notations are not clearly defined, like $\\mathcal{B}(\\reals^d)$ and $\\Delta_{\\Y'}$.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "15 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers the problem of constructing convex surrogates for supervised learning tasks, and provides lower bounds for the convex consistency dimension, which is the lowest prediction dimension with a consistent convex surrogate. Reviewers felt that paper was well-written, and that the techniques are novel and generally interesting. In particular, the authors use their framework to resolve open questions of Frongillo and Kash (2015) and Dearborn and Frongillo (2020). However, given that the topic is somewhat niche for the NeurIPS community, the authors are encouraged to incorporate the reviewers' suggestions to better convey the significance of their results to the broader community.
Decision: Accept (Poster)