Surrogate Regret Bounds for Polyhedral Losses
Authors: Rafael Frongillo
Bo Waggoner
Venue: NeurIPS 2021 Poster (2021)
Keywords: surrogate regret bounds
excess risk bounds
polyhedral losses
calibration
property elicitation

Abstract: Surrogate risk minimization is an ubiquitous paradigm in supervised machine learning, wherein a target problem is solved by minimizing a surrogate loss on a dataset.  Surrogate regret bounds, also called excess risk bounds, are a common tool to prove generalization rates for surrogate risk minimization.  While surrogate regret bounds have been developed for certain classes of loss functions, such as proper losses, general results are relatively sparse.  We provide two general results.  The first gives a linear surrogate regret bound for any polyhedral (piecewise-linear and convex) surrogate, meaning that surrogate generalization rates translate directly to target rates.  The second shows that for sufficiently non-polyhedral surrogates, the regret bound is a square root, meaning fast surrogate generalization rates translate to slow rates for the target.  Together, these results suggest polyhedral surrogates are optimal in many cases.

Surrogate Regret Bounds for Polyhedral Losses
Rafael Frongillo University of Colorado Boulder raf@colorado edu
Bo Waggoner University Colorado Boulder bwag@colorade edu
Abstract
Surrogate risk minimization is ubiquitous paradigm in supervised machine learning, wherein target problem is solved by minimizing a surrogate loss on a dataset. Surrogate regret bounds, also called excess risk bounds, to prove generalization rates for surrogate risk minimization. While surrogate regret bounds have been developed for certain classes of loss functions, such as proper losses, general results are relatively sparse. We provide two general results. The first gives linear surrogate regret bound for any polyhedral (piecewise-lineal and convex) surrogate, meaning that surrogate generalization rates translate directly to target rates. The second shows that for sufficiently non-polyhedral surrogates, the regret bound is a square root, meaning fast surrogate generalization rates translate slow rates for the target. Together, these results suggest polyhedral surrogates are optimal in many cases.
common tool
1 Introduction
In supervised learning, our goal is to learn a hypothesis that solves some target problem given labeled data. The problem is often specified by target loss that is discrete in the sense that the prediction lies in a finite set, as with classification, ranking, and structured prediction. As minimizing the target l over data is typically NP-hard, instead minimization. Here surrogate loss function L is chosen and minimized instead of the target f. A link function & then maps the surrogate predictions target predictions.
the general paradigm of surrogate risk
Naturally, a central question in surrogate risk minimization is how to choose the surrogate L. A minimal requirement is statistical consistency, which roughly says that approaching the best possible surrogate loss will eventually lead to the best possible target loss. A more precise goal is to understand the rate which this target minimization occurs, called the generalization rate: how quickly the target loss approaches the best possible, in terms of the number of data points. In other words, if we define the regret of hypothesis to be its performance relative to the Bayes optimal hypothesis, wish to know how quickly the Ê-regret approaches zero.
Surrogate regret bounds are a common tool to prove generalization rates for surrogate risk mini- mization, by bounding the target regret as a function of the surrogate regret. This bound allows generalization rates for surrogate losses-of which there are many, often leveraging properties of L like strong convexity and smoothness-to imply rates for the target problem. Roughly speaking, surrogate regret bound takes the form
V surrogate hypotheses h, Regret, h) < <( (Regret, (h)),
where the regret transfer function Ç R4 + R4 controls how surrogate regret translates to tar- get regret. For example, if we have a sequence of surrogate hypotheses h2 achieving a fast rate Regret, (h,) (1)nn,, and we have regret transfer of ((e) = Ve, then we can only guarantee slower target rate of Regret, (t = O(1/VT). The ideal regret transfer is linear, i.c. ((e) = C-e for some C > 0, which would have directly translated the fast-rate guarantee the target.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

Much is known about surrogate regret bounds for particular problems, especially for binary clas- sification and related problems like bipartite ranking: see 1.1 for a discussion of the literature. General results which span multiple target problems, however, are sparse. Furthermore, we still lack guidance as to which surrogate will lead to the best overall target generalization rate, as this rate depends on both the surrogate generalization rate and the regret transfer function. For example, consider the choice between a polyhedral (piecewise-linees and convex) surrogate, like hinge loss, or smooth surrogate like exponential or squared loss. The surrogate rate for polyhedral losses will likely be a slower (11 vT), whereas a faster O(1/n) rate is typical for smooth surrogates- what is the tradeoff when it comes to the regret transfer function S, which ultimately decides the target generalization rate? To answer these types of questions, we need more general results.
Our first result is a general surrogate regret bound for polyhedral surrogates. Perhaps surprisingly, we show that every consistent surrogate in this class achieves a linear regret transfer, meaning their surrogate generalization rates translate directly to target rates, up to constant factor.
Theorem 1 (Linear bound for polyhedral). Let I. be any polyhedral surrogate and ab any link function such that (I., ap) is consistent for the target loss E. Then I. satisfies Equation I with a linear Ç.
The recent embedding framework of Finocchiaro et al. [10] shows how construct consistent polyhedral surrogates for any discrete target loss: Theorem 1 additionally endows these surrogates with linear regret bounds. The same framework shows that every polyhedral loss is consistent surrogate for some discrete target. Theorem I therefore immediately applies to the Weston-Watkins surrogate [31]. Lovász hinge [10. 33), and other polyhedral surrogates in the literature currently lacking regret bounds.
We also give a partial converse: If the surrogate is sufficiently "non- mhon-polyhedral", i.c. smooth and locally strongly convex, then Ç cannot shrink faster than a square root. For these losses, therefore, even fast surrogate generalization rates would likely translate to slow rates for the target.
Theorem 2 (Lower bound for "non- nonn-polyhedral", Let L be a locally strongly convex surrogate with locally Lipschitz gradient. If L satisfies Equation for a target loss l, then there exists e >> 0 such that, for all small enough 0, have {(c) 2 c vT.
While it may seem intuitive that (= v- v- for strongly convex losses, it is well-known that losses like exponential loss for binary classification also have Ç = v- even though they are neither strongly convex nor strongly smooth [4]. Theorem 2 offers an explanation for this phenomenon, and together with Theorem clarifies an intriguing trend in the literature: ( is typically either linear or square-root.
Taken together, our results shed light on the dichotomy expressed above:
slower polyhedral surrogate rates of ((1/ /ni) will translate to the target unchanged, while most smooth surrogates, even if achieving a fast surrogate generalization rate of O(L/n), will likely yield the same target rate of (n)/ Our results therefore suggest an inherent tradeoff fast surrogate rates and optimal regret transfer, phenomenon also observed by Mahdavi et al. [17] for binary classification. In particular, our results suggest that polyhedral losses may achieve an overall generalization rate to the target problem with the optimal dependence on the number of data points.
The proof of our upper bound, Theorem 1, is nonconstructive. After proving the main results (Sections 3 and 4), we make it constructive in Section 5. Specifically, the regret transfer function for polyhedral loss can be bounded by (()) I a / where the constant is of the form a = og ort, - ar-- Each component of a depends only on its respective object e, L., and vb. A corollary of the derivation is that polyhedral loss L. and link s are consistent for if and only if vé is e-separated, condition introduced in Finocchiaro et al. [10].
1.1 Literature surrogate regret bounds
Surrogate regret bounds were perhaps developed first by Zhang [37], as a method to prove statistical consistency for various surrogate losses for binary classification. These results were then generalized by Bartlett et al. [4] for margin losses, and Reid and Williamson [26] for composite proper losses.
Many of these polyhedral surrogates mentioned are actually known be inconsistent for their intended target problems. Nonetheless, the embedding framework of Finocchiaro et al. [10] shows that any polyhedral surrogate is consistent for some target problem, namely the one that it embeds. It is to this embedded target loss function, rather than the intended target, that our linear regret bounds apply.

---

These latter works and others give fairly complete picture for binary classification: a characterization of calibrated surrogates, and precise closed forms for the optimal Ç for each. By extension, close variations on binary classification are also well-understood, such as cost-sensitive binary classifica- tion [28], binary classification with an abstain/reject option [3, 8, 34], bipartite ranking [1, 13, 18], and ordinal regression via reduction to binary classification [22]. For multiclass classification, we have nice consistency characterizations with respect to 0-1 loss [30], with some surrogate regret bounds [9, 23).
Beyond binary classification and 0-1 loss, our knowledge drops off precipitously, with few general results. There are some works which provide partial understand for specific target problems. For example, in the problem of multiclass classification with an abstain option, Ramaswamy et al. [25] give three consistent polyhedral surrogates (two of which are commonly used as inconsistent surrogates for 0-1 loss), along with linear surrogate regret bounds. (See also Ni et al. [19, Theorems 7 & 8] and Charoenphakdee et al. [6. Theorem 8] for other surrogate regret bounds for the same problem.) Ramaswamy et al. [24) show how to extend these surrogates to nested, hierarchical versions, again providing linear regret bounds. Motivated by these polyhedral surrogates, together with examples arising in top-k prediction [16, 32] and other structured prediction problems [33], Finocchiaro et al. [10] introduce embedding framework for polyhedral surrogates. This framework shows that all polyhedral surrogates are consistent for some discrete target problem, and vice versa, but do not provide surrogate regret bounds. Our results fill this gap, giving linear regret bounds for all polyhedral losses, and thus all discrete target problems.
Perhaps closest in spirit to our work are several recent works on general structured prediction problems. Ciliberto et al. [7, Theorem 2] and Osokin et al. [21, Theorem 7] give surrogate regret bounds for quadratic surrogate, for general class of structed prediction problems. Blondel [5, Proposition 5] gives surrogate regret bounds for a tighter class of quadratic surrogates based on projection oracles. Nowak-Vill Vila et al. [20, Theorem 4.4] give even more general bounds, using broader class of surrogates based on estimating a vector-valued expectation. All of these works apply to broad range of discrete target problems. The main difference to our work is that their upper bounds are all for strongly convex surrogates, 2 whereas ours are for polyhedral surrogates. Osokin et al. [21, Theorem 8] and Nowak-Vill et al. [20, Theorem 4.5] also provide lower bounds, in the same spirit as our Theorem but only for the classes of surrogates they study. In particular, our results recover their bounds up to constant factor.
Finally, in the binary classification setting, some works have used surrogate regret bounds to study the relationship between generalization rates for the surrogate and target, as discussed above. Zhang et al. [36] give detailed results about how surrogate regret bounds actually convert the surrogate rate to the target rate, by carefully analyzing the behavior of the regret tranfer function near O. They argue that hinge loss achieves strictly better rates than smooth surrogates like logistic and exponential loss; notably, though, this claim implicitly assumes that generalization rate is the same for all surrogates under consideration. By contrast, Mahdavi et al. [17], as we do, consider that the surrogate generalization rate may depend on the choice of surrogate. They study particular family of smoothed hinge losses, and show a direct tradeoff: smoother losses yield faster surrogate generalization rates, but "slower" regret transfers. Without placing further assumptions therefore, Mahdavi et al. [17] observe the same general phenomenon as we do: while smoothness may help surrogate generalization rates, it can hurt the regret transfer just as much. In particular, without further assumptions, polyhedral surrogates appear to achieve optimal overall generalization rates.
the data,
2 Preliminaries
Target problems. We consider supervised machine learning problems where data points have features in X' and labels in V, a finite set. The target problem is to learn hypothesis mapping X to a report (or prediction) space R. possibly different from y. For example, binary classification has y= = (-1, whereas for ranking problems R may be the set of permutations of ). In this paper, we assume R is finite set. The target problem is specified by the target loss E: R - RY which maps report (prediction) r E R to the vector (rr) of nonnegative loss values for each label,
'These works express surrogate regret bounds with --1 appearing on the henthaad side of eq. (1), and thus the terms "upper bound" and "lower bound" are reversed from their terminology.
3

---

Le. f(r) = (E(r)y)yey. Given a hypothesis : X - R and data point (z, v) E X' x V, the loss is E(g(z)) y.- We make a minimal -on-redunanccy assumption on f. formalized in Section 2.1. We may refer to & as a discrete target loss to emphasize our assumption that R. and y are finite.
Surrogate problems. We recall the surrogate risk minimization framework. First, one constructs surrogate loss function L : R + R.y. Then, one minimizes it to learn hypothesis of the form h : X' + IR.. Finally, one applies link function da : IRd - R, which maps h to the implied target hypothesis sb o h.3 In other words, a surrogate prediction h(x)) E implies a prediction (h((z)) E R for the target problem. For example, in binary classification, the target problem is given by 0-1 loss, (r) = 1rr * y). with surrogate losses typically defined over IR. max(1 uy, 0), logistic Common surrogate losses for 0-1 loss include hinge loss Lhingo exp(- These surrogates loss (u), = In (1 + exp(-9ru)), and exponential loss Lexp("),
are typically associated with the link v u + sign(u), (u). which maps negative predictions to -1 and nonnegative predictions to +1, breaking ties arbitrarily at O.
Surrogate regret bounds. The suitability and efficiency of a chosen surrogate is often quantified with a surrogate regret bound. Formally, the surrogate regret of with respect to data distribution D is given by (h; D) )(D [h(())) ix- Exx ()xD L(M( where the minimum is taken over all measurable functions. (One may equivalently assume the Bayes optimal hypothesis is in the function class.) Given h, the larget regret of the implied hypothesis vi o h is (e o h; D) = ExX,Y)< (()()( - inf E(XY))~ E(N' (()()))), where we recall that s is the link function.
A surrogate regret bound answers the following question: when we minimize the surrogate regret at rate f(n), given data points, how fast does the target regret diminish? Formally, say that <: R4 - IR, is a regret transfer function if Ç is continuous at and satisfies <(0) = O. Given a rerget transfer function Ç, we say that (I, v) guarantees a regret transfer of Ç for i
YD, vh X - R Rele' o h; D) S Ç( R2 (h;
We note that a classic minimal requirement for (I, v)) is that they be consistent for f, which is the case if there exists any regret transfer & guaranteed by (I, x)) for E [29]. In other words, consistency implies that Ry (h; D) + 0
Re(w o h; D) - O, but says nothing about the relative rates.
Polyhedral surrogates. A function f Rd + F called polyhedral if it can be written as a pointwise maximum of finite set of affine functions [27, $ 19]. The epigraph of polyhedral function is a polyhedral set, i.c the intersection of a finite set of closed halfspaces; thus polyhedral functions are always convex. We say a surrogate loss _2d R is polyhedral if, for each fixed E y, the loss as a function of prediction, i.c. r + L(r)g, is polyhedral.
2.1 Property elicitation and the conditional approach
Our technical approach is based on property elicitation, which studies the structure of E and T. as they relate to Ay. This involves a conditional perspective. Given a data distribution on X' x V, for (X,Y) Y) ~ D. we consider the format of possible target predictions g(x) = r E R: surrogate predictions /((x)=
E IR; and conditional distributions Pr[- X] = p E Ay. By dropping the role of the hypotheses and the feature space X, we can focus on the relationships of the functions ((r), and L(u)y, and the conditional distribution p.
In particular, in notation the expected L-loss of prediction u distribution p is simply the inner product (p, I(u)). The Bayes risk of I, is L(p) = inf (p. I(w)), and similarly the Bayes risk of E is {(p) inf (p, {(r)). We abuse notation to define the conditional surrogate regret Ry(u, p) = (p. I(u)) I(p). and similarly the conditional target regret P)(r.p) = (p, )(r) - -(()). Given regret transfer function Ç, we say (L, 1b) guarantees a conditional regret transfer of ( for é if, for all p E Ay and all Rd (V((),), p) I ((Rz(u,)),
The following is a direct result of Jensen's 's inequality, using that (h; Ex R, where px is the conditional distribution on Y given X.
'The term "link function" can carry a more specitic meaning in the statistics literature, for example when discussing generalized linear models. Our usage here is more general: any map from surrogate reports to target reports is valid link function, though perhaps not calibrated one.

---

Observation 1. (L. +) guarantee a regret transfer of f.or E.
(L. 6) guarantee a conditional regret transfer of f t, and Ç is concave, then
Property elicitation. To begin, we define property, which is essentially a statistic or summary of
distribution, such as the mode. We then define what means for a loss function to elicit a property. We write r; Ay = R as shorthand for I' : Ay - 2 {0}.
Definition (Property, level set). A property is function I' : Ay = R, for some set R. The level set of I' for report r is the set I {p Ay r E l(p)).
The following definition applies both to target losses and surrogate losses.
Definition 2 (Elicits, report space). A loss function f R RRZ where the domain R is called the report space, elicits property r: Ay 3 R if
Vp E Ay, rpp) = arg min (p. f(r)) pr))]f](p). rER
(3)
As each loss I elicits a unique property, we refer to it as prop!/]. In particular, we will consistently use the notation = prop[L] where L is a surrogate loss with report space R", and we will use y prop[[] where is target loss with finite report space R. For example. prop[C20] is simply the mode of p. given by mode(p) = {-1,1) p = 1/2, and mode(p) = {sign (2p 1)} otherwise.
We will assume throughout that the target loss & R - Ry is non-redundant, meaning that all target reports r E R are possibly uniquely optimal. Formally, letting = prop[é]. we suppose that for all r E R. there exists E Ay with r(p) = {r].
Calibration and consistency. It is known that consistency implies the weaker condition of cali- bration, which implies the still-weaker, but very useful, condition of indirect elicitation. To define these conditions, consider L, vb, and y = prop[e]. Recall that r(p) is the set of target reports that are optimal for p. The typical definition of indirect elicitation, which we reformulate below, is as follows: surrogate- link pair (L, 15) indirectly elicits y if u E [p)p[[]pp) = suu) E 7pp) for all p E Ay. Note that if (u) E (p). then u is "bad" (suboptimal) surrogate prediction for p. Let (p)) = (Rr (u,
(u)) é }())). the set of expected surrogate losses resulting from bad predictions. Thus, we may equivalently state indirect elicitation as the requirement that suboptimal surrogate reports be bad, which clarifies the relationship to calibration: calibration further requires nonzero gap between the expected loss of "good" report and that of any bad one.
Definition 3 (Indirectly Elicits, Calibrated). Let E be target loss and 7 prop[e]. A surrogate-link pair (L, t) indirectly elicits y 0 &f (L,,,e(p) for all E Ay. The pair (L, v) is calibrated for E O < inf (p)) for all p E Ay-
Fact 1 ([4, 29]). Let E R TR.Y be target loss with finite R. and y. If a surrogate and link (I, are consistent for f, then (I, 1b) are calibrated for L.. If (I., 18 are calibrated for E, then they indirectly elicit f.
For example, it is well-known that hinge loss Thinge is calibrated and consistent for 0-1 loss lzo using the link &b + sign(u). Recall that loo clicits the mode. One can verify that indeed (Lninge: vi) indirectly elicit the mode; for example, SLnnneerhheec (0) = Lsimee to (1) = [I, oo) and
B B 6o (1/2) neither of which contain 0.
3 Upper Bound: Polyhedral Surrogates
In this section, we describe the proof of Theorem 1, that polyhedral surrogates guarantee linear regret transfers. At a high level, the proof (whose details appear in Appendix A) has two parts:
1. Fix p E Ay. Prove regret bound for this fixed p, namely a constant ap such that Re(tbu),p)) S a,RRy (u, p) for all u E Rdd
2. Apply this regret bound to each in a carefully chosen finite subset of Ay. Argue that the
maximum ap from this finite set suffices for the overal regret bound.
'Technically, this detinition differs from the one given in literature [10, 11]. but the two are equivalent for finite elicitable properties.
5

---

The first part will actually hold for any calibrated surrogate. The second part relies on crucial fact about polyhedral losses their properties I = prop L cover the whole simplex with only finite number of polyhedral level sets [10]. Thus, although the prediction space I2 is infinite, one can restrict to just finite set of prediction points and always have a global minimizer of expected surrogate loss.
3.1 Linear transfer for fixed p
First, we establish linear transfer function for any fixed conditional distribution p. This statement holds for any calibrated surrogate, not necessarily polyhedral.
Lemma 1. Let & R - TR be discrete larget loss and suppose the surrogate I Rd - R2 and
link 3 R2 R are calibrated for E. Then for any Ay, there exists Op 2 0 such that, for all
E R4.
Re(v(u),p) S apRr(u
While useful, this result is somewhat nonconstructive and potentially loose. In Section 5, we unpack the constant Op for polyhedral losses in particular.
3.2 Linear overall transfer function
Given Lemma we might hope to obtain that, for any calibrated surrogate, there exists a = sup, Op such that Re(v(u)) p') I (u. for all p'. However, know this is false in general: not all surrogates yield linear regret transfers! Indeed, for many surrogates, the supremum will be +00.
However, polyhedral surrogates have special structure that allows present some tools that hold for general surrogates, then the key implication from I. being polyhedral. Lemma 2 ([12)). (L, (b) indirectly elicits y, then I = prop []] refines "y in the sense that, for all E Rd there exists R such that I., C %/-
show a is finite. We first
The next lemma states that surrogate regret is linear in p on any fixed level T.. of prop[L]. By combining this fact with Lemma 2. we obtain that target regret is linear on these level sets as well. Lemma 3. Suppose (L, v) indirectly elicits 7 = prop[e] and let prop[L]. Then for any fixed u, n² Rdd and R, the functions -u, and Re(r,-) are linear on Tu- in their second arguments.
A key fact we use about polyhedral losses is that they have finite set of optimal sets. Lemma 4. If L Rd + R is polyhedral, then I = prop[L] has a finite set of level sets that union Ay. Moreover, these level sets are polytopes.
We are now ready to restate the main upper bound and sketch a proof.
Theorem (Theorem restated). Suppose the surrogate loss L Rdd > R and link sb RRd + R are consistent for the target loss é R - R.Y. If L is polyhedral, then (L, v) guarantee a linear regret transfer for E, i.e. there exists 2 0 such that, for all D and all measurable h X - Rdd
Re( o h; D) S (h;
The key point of the proof is that, by Lemma 4, the polyhedral loss L has finite set U Rd of predictions such that (a) for each U. the level set To is polytope, and (b) Uueu = Ay. Let Q be the finite set of all vertices of all these level sets. For any vertex E Q, we have linear regret transfer for this fixed q with constant ag from Lemma 1. Lemma allows us to write the regret of a general convex combination of the regrets of its containing level set's vertices. So obtain bound of a = maxge ag.
Lower bound
In this section, we show that if surrogate loss is sufficiently "pon-polyhedral" then the best regret transfer it can achieve ((c) on the order of ve. (Proofs are deferred Appendix B.) Specifically, consider relaxation of L being both strongly smooth and strongly convex, as now formalize.

---

Let I = pr and y = prop[e]. We will assume L is strongly smooth everywhere and strongly convex around some boundary report for I,, f, which we define to be Mo E IR such that, for some r, r R, there exists distribution Po such that po E I un i. Nrr. For the conditional distribution Po. the surrogate report ug minimizes expected L-loss, and it may link to either or r', as either of these minimize expected E-loss. Recall that an open neighborhood of uo is an open set in Rd containing ugg
Assumption 1. L: Rd + RY is a surrogate and ab Rd + R a link, consistent with the discrete target é: R + R.", satisfying the following: (i) For all y E V the function L(-), is differentiable (ii) For some a > O and some boundary report th E IRd for L, f, the expected loss function u + (p, L()) is a-strongly convex on an open neighborhood of uo.
with locally Lipschitz gradient.
This assumption is quite weak. In particular, because l has finite report set R, boundary reports essentially always exist whenever (L, eb) indirectly elicits f. In particular, as the level sets of y are closed, convex, and union the simplex [10, 15], there must be some pair of reports r' R with yr n 3r' * 0. We can then take Po E "r n Yr', and any uy E T(po). One caveat is that we may have [pp)) 0. While some surrogates may fail to have minimizer for some distributions p. this typically happens when p is on the boundary of the simplex, and not generally on the boundary between level sets. For example, consider exponential loss Texp(1) (u)y exp(-uy). where prop expp) (0) = proppreeee Tx (1) = 0, but we still have prop [Teep] (1/2) = (0).
The following result is main lower bound.
Theorem (Stronger version of Theorem 2.). Suppose the surrogate loss and link ab satisfy a regret transfer of C for target loss l. If I., th, and satisfy Assumption 1, then there exists 0 such that, for some e* > for all 0 S < <c, c(c) 2 evC.
The key idea of the proof is to fix a boundary report uo and consider sequence of distributions Px - Po as Å + O. Target regret R& (v)())) px) shrinks linearly in X, but surrogate regret Ry (wo, Px) shrinks quadratically. The latter holds roughly because expected surrogate loss is strongly convex in some neighborhood of un and is strongly smooth elsewhere."
Theorem 4 captures a wide range of surrogate losses beyond those that are strongly convex and strongly smooth. For example, exponential loss Lexp(u) exp(-up) is not strongly convex, but does satisfy Assumption 1; for part (ii), the boundary report is ug O as we saw above, and Lexp is 1/ //e-strongly convex on (-1,1)= 3 ug.
As another example, consider Huber loss for binary classification. Here y = [ space is R. and Huber loss can be defined by letting the hinge loss be max - ry} and setting L(T), = t² if < 2, else 4(t 1). Theorem 4 does capture Huber, but needs the strength of Assumption (ii) as Huber strongly convex on [-1, 1] but linear outside that interval.
} and the prediction
5 Unpacking the constant for polyhedral losses
Our main upper bound for polyhedral losses, Theorem 1, is mostly nonconstructive: it says polyhedral surrogates have some a such that Re(sh h; D) a R2 (h; D). In this section, we make the result constructive by unpacking the implications of consistency for polyhedral surrogates. Proofs appear in Appendix C.
5.1 Contribution from the target, surrogate, and link
We will give a bound on the constant of the form a S aig aL ag i.c. one component each relating to the structure of the target loss, surrogate loss, and link. First, we will derive ag using the theory of Hoffman constants from linear optimization [14]. Then, we will show that any link for a consistent polyhedral loss must satisfy condition called c-separation, introduced in [10]. We will set axp = With a simply an upper bound on the target loss, we will finally prove a S ar az Otp.
A map g: A + B is locally Lipschitz if for every E A there is an open neighborhood U of such that g is Lipschitz continuous.
6 A tempting alternative is to fix distribution po and consider sequence of predictions. We know from Lemma I that this approach will fail, however: for any consistent surrogate and any fixed po. there is linear regret transfer if we restrict to po.
7

---

5.1.1 Hoffman constants
The intuition we explore here is the linear growth rate of given polyhedral function as we move away from its optimal set. In particular, consider the expected loss u +> (p. [(u)). Expected loss should grow linearly with distance from the optimal set, which happens to be ['p). In particular, the worst growth rate is governed roughly by the smallest slope of the function in any direction. This is captured by the Hoffman constant of an associated system of linear inequalities. In Appendix C, we use Hoffman constants to obtain the following result, where we define HL.P"
Lemma 5 (114). Let L Rd + R. be a polyhedral loss with = prop[.]. Then for any fixed p. there exists some smallest constant HI.p 2 O such that d (u, (p)) S HI.pRr((. for all Rd
To foreshadow the usefulness of H. recall the proof strategy of the upper bound: use Lemma to obtain constant Op for each p; then carefully choose finite set of p's and take the maximum constant. In the same way, we will be able to set the "loss" constant ar = max, H. First, however, we will need to investigate separated links.
5.1.2 Separated link functions
link is c-separated if, for all pairs of surrogate reports u, u" such that u" optimal for the surrogate and u links to suboptimal target report, we have I|u" u||oo > The definition was introduced by Finocchiaro et al. [10].
Definition 4 (Separated Link). Let properties I' Ay = IR and y Ay = R be given. We say link e Rd + R e-separated with respect to I' and y if for all u E IR with ((() & r()), we have
do (u, [p)) > where d (u, A) = infae. ||u allxc. Similarly,
say 2/ is e-separated with respect to L and f if is e-separated with respect to prop[L] and propic].
Recall from the previous subsection that Hoffman constants allowed us to show that polyhedral expected losses grow linearly as we move away from the optimal set. Now, e-separated link functions allow us to guarantee that we move at least a constant distance from the optimal set before we start linking to an "incorrect" report r' R. But when does polyhedral loss have an associated e-separated link?
Finocchiaro et al. [10] showed that e-separated links for polyhedral surrogates are calibrated. We show that the converse is in fact true: every calibrated link is e-separated for some >> 0. The proof follows similar argument to that of Tewari and Bartlett [30, Lemma 6).
Lemma 6.
Let polyhedral surrogate L I R discrete loss é : R IR and link sb RRd R be given such that (L, v) is calibrated with respect to f. Then there exists > O such that sb is e-separated with respect to I = prop[L] and 7 - prop[e].
5.1.3 Combining the loss and link
We can now follow the general proof strategy of the main upper bound, but constructively. Given Lemma 6, we can make the following definition.
Definition 5 (Ew). If (L, ( are calibrated for E, then let cv - sup(e v is e-separated].
We will also need upper bound C₁- max,, Re(r,p) p) on the regret of f. Since Rę is convex in p. in particular this maximum is achieved at a vertex of the probability simplex.
Definition (Ct). Given discrete loss E: R + y define C2- = max,, wEy E(r)y - l(r')y-
Recall that Lemma 4 gave that, if L is polyhedral, then I' = p has a finite set of cull-dimensional level sets, each a polytope, that union to the simplex.
Definition 7 (H Given polyhedral surrogate loss I. Rd TR. let Q be the set of all vertices of the full-dimensional level sets of T prop[L], and define H2 = maxpee HL,p-
Theorem 5 (Constructive linear transfer). Let : R + Ey be discrete target loss, L Rdd Ry be a polyhedral surrogate loss, and vb : Rd - R a link function. If (L, 16 are consistent,or then
CeHL R2 (h;
(4h, Re( h; D) <
6o
8

---

The proof closely mirrors the proof of the nonconstructive upper bound. Theorem 1, but using the constructive constants Ce, H Ep derived above. To summarize, we have shown the following.
Theorem 6. Let l R + R be a discrete target loss, L: L. + Ry be a polyhedral surrogate loss, and to Rd + R a link function. The following are equivalent:
1. ()) is consistent for L.
2. vb is c-separated with respect to I. and f for some e > 0.
3. (L. guarantees a linear regret transfer for l.
Furthermore, if any of the above hold, then in particular (L, v) guarantees the regret transfer
<(I) = Cr t.
5.2 Further tightening
While our goal is not to focus on exact constants for specific problems, we remark on few ways Theorem 5 may be loose and how could compute the tightest possible constant a* for which [ o h; D) S a" Rr (h; D) for h and D. In general, for fixed p, there is some smallest og such that R1 (v) S oz Rr. (u,p) p) for all u. Then, it follows from our results that a² maXpe2 o for the finite set used the proof, i.e. the vertices of the full-dimensional level sets
prop[L.)
Above, we bounded o S
CeHiie The intuition that some u at distance 2 fv from [w)).
co
optimal set, may link to a "bad" report r (u)) & (p). The rate which L grows is at least cv while the target regret may be as high as HL,ps so the surrogate loss at u may be as small as HE,,
C. = max,' of .'))..p'). The ratio of regrets is therefore bounded by Cr
The tightest possible bound, on the other hand, is a* suPa:e(w)g(<(p) (v(2))) be smaller if the values of numerator and denominator only be eg-close to the optimal set when it links to reports (b()) with lower target regret; or L may have smaller slope in the direction where the link's separation is larger than
[g(pp) This bound can correlated across For example, may
To illustrate with a concrete example, consider the binary encoded predictions (BEP) surrogate of [25] for the abstain target loss, [(r, y) = if 1, otherwise (rr, 3/ = [ # y). The surrogate involves an injective map B y - {-1, 1, 1)dd for d [log [3']]- It is L(u)y max where (-)+ indicates taking the maximum of the argument and zero. The associated link is (u)) = if minj-1...d [u,] 1. otherwise (u) arg min Byy) u||oco
u B(yd))
One can show that for p ky. i.e. the distribution with full support on some E V, I(u)g doe (u, (p)) exactly, giving HL.p = 1. It is almost immediate that cu. = 2- Meanwhile, Re(r, p) < 1, giving us an upper bound a < 1/2
[1)(1) = 2. In fact, this is slightly loose: the exact constant, given in
[25] is 1. The looseness stems from the fact that for p = 6y. the closest reports u to the optimal set, ie. at distance only 6v 1/ away, do not link to reports maximizing target regret; they link to the abstain report 1, which has regret only 2- With this correction, and an observation that all linking to reports y' * are at distance at least from l'(p), we restore the tight bound < 1. A similar but slightly more involved calculation can be carried out for the other vertices p E to be all vertices of the form f 5
g which turn out
Finally, while we use || lloe to define the minimum-shee -lope H, and the separation Cg. principle one could use another norm. One reason for restricting to || looo is that it is more compatible with Hoffman constants. However, all definitions hold for other norms and so does the main upper bound, as existence of an H, and é in ||. 1.x imply existence of constants for other norms. These constants may change for different norms, and particular, the optimal overall constant may arise from norm other than || ll

---

Discussion
We have shown two broad results about regret tranfer functions for surrogate losses. In particular, polyhedral surrogates always achieve a linear transfer, whereas "non-pol poon-polyhedral" surrogates generally square root. Section outlines several directions to further refine the bound for polyhedral surrogates, Beyond these directions, interesting question is to what extent our results hold when the label set or report set are infinite. For example, when the labels are the real line, pinball loss is polyhedral yet elicits a quantile, a very different case than the one study. In particular, Lemma will not give a finite set of optimal sets in this case. Nonetheless, we suspect similar results could go through under some regularity assumptions. Finally, in line with our results, would like to better understand the tradeoff between smoothness of the surrogate and the overall generalization rate. One important direction along these lines is to extend the analysis of Mahdavi et al. [17] beyond binary classification.
Broader Impacts
As theoretical work, the likely impacts of this paper take the form of downstream research and applications. Instead of direct applications, anticipate this work leading to more investigation of surrogate losses to improve discrete prediction tasks. It may inform practitioners' choices of which surrogate losses they use for supervised learning tasks. Of course, such machine learning tasks can be solved for ethical or unethical purposes. We do not know of particular risk of negative impacts of this work beyond risks of supervised machine learning in general.
Acknowledgments and Disclosure of Funding
We thank Stephen Becker, Jessie Finocchiaro, and Nishant Mehta for insights, discussions, and references. This material is based upon work supported by the National Science Foundation under Grant No. IIS 104-444
References
[1] Shivani Agarwal. Surrogate regret bounds for bipartite ranking via strongly proper losses. The Journal of Machine Learning Research, 15(1):1653-1674, 2014.
[2] Franz Aurenhammer. criterion for the affine equivalence of cell complexes in R d and convex polyhedra in d+1. Discrete & Computational Geometry, 2(1):49-64, December 1987. ISSN 0179-5376, 1432-0444.
doi: 10.10077/F001888700 URL http::/ltiii springer com/
article/10. 1007 1007/ /BF02187870.
[3] Peter L. Bartlett and Marten H Wegkamp. Classification with a reject option using a hinge loss. Journal of Machine Learning Research, ((Aug):1833-184 2008.
[4] Peter I.. Bartlett, Michael I. Jordan, and Jon D. McAuliffe.
Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473) 2006. URL candfonnint cot. /ooi /tt/ooii//////// 10. 118800111440000000001
[5] Mathieu Blondel. Structured prediction with projection oracles. Advances neural information processing systems, 32: 12:12155-1216, 2019.
[6] Nontawat Charoenphakdee, Zhenghang Cui, Yivan Zhang, and Masashi Sugiyama. Classifi- cation with rejection based on cost-sensitive classification. In International Conference on Machine Learning, pages 1507-1517. PMLR, 2021.
[7] Carlo Ciliberto, Lorenzo Rosasco, and Alessandro Rudi. A consistent regularization approach for structured prediction. Advances neural information processing systems, 29:4412 4420. 2016.
[8] Corinna Cortes, Giulia DeSalvo, and Mehryar Mohri. Learning with rejection. In International Conference on Algorithmic Learning Theory, pages 67-82. Springer, 2016.
[9] John Duchi, Khashayar Khosravi, and Feng Ruan. Multiclass classification, information, divergence and surrogate risk. The Annals of Statistics, 46(6B):3246-32 2018.
10

---

[10] Jessie Finocchiaro, Rafael Frongillo, and Bo Waggoner. An embedding framework for consistent polyhedral surrogates, Advances in neural information processing systems, 2019.
[11] Rafael Frongillo and lan Kash. General truthfulness characterizations via convex analysis. In Web and Internet Economics, pages 354-370. Springer, 2014.
[12] Rafael M Frongillo and Ian A Kash. Elicitation complexity of statistical properties. Biometrika, 2020.
[13] Wei Gao and Zhi-Hua Zhou. On the consistency of auc pairwise optimization. In Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015.
[14] Alan J Hoffman. On approximate solutions of systems of linear inequalities. Journal of Research of the National Bureau of Standards, 49(4), 1952.
[15] 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.
[16] Maksim Lapin, Matthias Hein, and Bernt Schiele. Loss functions for top-k error: Analysis and insights. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. pages 1468-1477, 2016.
[17] Mehrdad Mahdavi, Lijun Zhang, and Rong Jin. Binary excess risk for smooth convex surrogates. arXiv preprint arXiv: 1402. 2014.
[18] Aditya Krishna Menon and Robert C Williamson. Bipartite ranking: risk-theoree perspective. The Journal of Machine Learning Research, 17(1):776-66677, 2016.
[19] Chenri Ni, Nontawat Charoenphakdee, Junya Honda, and Masashi Sugiyama. On the calibration of multiclass classification with rejection. arXiv preprint arXiv: 1 /901 1905. 2019.
[20] Alex Nowak- Vila, Francis Bach, and Alessandro Rudi. A general theory for structured prediction with smooth convex surrogates. arXiv preprint 1902.09900000 00900........................ 2019.
[21] Anton Osokin, Francis Bach, and Simon ciccotte-ullien. On structured prediction theory with calibrated convex surrogate losses. In Advances in Neural Information Processing Systems, pages 302-313, 2017.
[22] Fabian Pedregosa, Francis Bach, and Alexandre Gramfort. On the consistency of ordinal regression methods. Journal of Machine Learning Research, 18:1-35, 2017.
[23] Bernardo Avila Pires, Csaba Szepesvari, and Mohammad Ghavamzadeh. Cost-sensitive mul- ticlass classification risk bounds. In International Conference on Machine Learning, pages 1391-1399, 2013.
[24] Harish Ramaswamy, Ambuj Tewari, and Shivani Agarwal. Convex calibrated surrogates for hicrarchical classification. In International Conference on Machine Learning, pages 1852-1860, 2015.
[25] Harish G Ramaswamy, Ambuj Tewari, and Shivani Agarwal. Consistent algorithms for mul- ticlass classification with an abstain option. Electronic Journal of Statistics, 12(1):530-554, 2018.
[26] Mark D Reid and Robert C Williamson. Surrogate regret bounds for proper losses. In Pro- ceedings of the 26th Annual International Conference on Machine Learning, pages 897-904, 2009.
[27] R.T. Rockafellar. Convex analysis, volume 28 of Princeton Mathematics Series. Princeton University Press, 1997.
[28] Clayton Scott. Calibrated asymmetric surrogate losses. Electronic Journal of Statistics, 958-992, 2012.
[29] Ingo Steinwart and Andreas Christmann. Support Vector Machines. Springer Science & Business Media, September 2008. ISBN 978-0-387-77242-44 Google-Books-ID: HUnqorp
[30] Ambuj Tewari and Peter L. Bartlett. On the consistency of multiclass classification methods. The Journal of Machine Learning Research, 8: 8:1007-1025, 2007. URL //dt acm. org/ citation. cf39222
[31] Yutong Wang and Clayton Scott. Weston-watkins hinge loss and ordered partitions. Advances in neural information processing systems, 2020.

---

[32] Forest Yang and Sanmi Koyejo. On the consistency of top-k surrogate losses. CoRR, 1901.11141, 2019. URL http:// http://axiw...raab///eeeee
11141.
[33] 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, 2018.
[34] Ming Yuan and Marten Wegkamp. Classification methods with reject option based on convex risk minimization. Journal of Machine Learning Research, 1 11(Jan): 11-130, 2010.
[35] Constantin Zalinescu. Sharp estimates for hoffman's s constant for systems of linear inequalities and equalities. SIAM Journal on Optimization, 14(2)3177-333, 2003.
[36] Jingwei Zhang, Tongliang Liu, and Dacheng Tao. On the rates of convergence from surrogate risk minimizers to the bayes optimal classifier. IEEE Trunsactions on Neural Networks and Learning Systems, 2021.
[37] Tong Zhang. Statistical behavior and consistency of classification methods based convex risk minimization. The Annals of Statistics, 32(1):56-88 -55566852222 2004.
12


Reviews:
[{"review_id": "HmBWCE2zC00", "reviewer": "Reviewer_auqc", "summary": "This paper provides general excess risk bounds result for a class of polyhedral losses for a general machine learning problem, where a prediction space and label space lie in a finite set. This covers many fundamental problems, e.g., classification, ranking, classification with rejection.  While such theoretical results have been quite well-studied for a family of strictly proper losses (a loss that can estimate the class probability (p(y|x)), less attention has been paid to other loss families. This paper shows that a polyhedral surrogate loss (i.e., piecewise-linear convex loss such as hinge loss) that is consistent with the target discrete loss has a linear excess risk transfer bound, which is desirable. Furthermore, the paper showed that a large class of non-polyhedral loss (including some strictly proper losses) cannot achieve the same result. On the other hand, such non-polyhedral losses have a slower rate than linear (square root). ", "questions": "", "limitations": "", "rating": 8, "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 main contributions of this paper are clear, impactful, and well-presented. It completely characterizes the excess risk transfer bound of any convex polyhedral losses. The discussion of related work is also appropriate and nice. The constructive linear transfer kindly provided in Section 5 is impressive. On the other hand, it would have been better if there are some illustrations (e.g., Figure, table) to help readers to understand this paper. For example, an illustration of the shape of polyhedral losses, a table to highlight the well-known non-polyhedral loss functions that Theorem 2 covers and does not cover. \n\nQuestions and comments:\n1. This paper delivers a strong theoretical result in the case where a prediction space and label space are finite sets. My impression is that this result is already very general in this submission. Is there a case where we have non-finite sets for prediction/label space yet polyhedral losses are used in the literature up until now, where the theory of this paper does not cover?\n2. Line 55: It seems the previous result by Finocchiaro et al. [8] suggested that the Lovasz hinge loss, in general, is inconsistent, and perhaps it is not applicable to Theorem 1 and the excess risk transfer bound should not exist. Maybe a few words about this in the manuscript would be useful if my understanding is correct.    \n\nMinor comments:\n1. Line 47: suprisingly -> surprisingly\n2. Line 109: Theeeorem - > Theorem\n3. Ref [21] in the manuscript: In my understanding, this work was only done by Clayton Scott (single author) and therefore \"et al.\" should be removed\n4. Ref [28] in the manuscript: In my understanding, this work was only done by Tong Zhang (single author) and therefore \"et al.\" should be removed\n\nMore references related to calibration/excess risk bound for other specific problems that the authors may want to include in the manuscript.\n\nBinary classification with rejection:\n\n[1] Cortes et al., Learning with rejection, ALT, 2016 (Theorem 3 - a variant of hinge loss with linear excess risk bound). \nFYI: There exists another work by the same authors where they used an exponential-based loss for this problem with calibration guarantee [2], but unfortunately the excess risk bound was not provided to my knowledge (but I guess it would be slower than linear).\n\n[2] Cortes et al., Boosting with abstention, NeurIPS, 2016 \n\nMulticlass classification with rejection:\n\n[3] Ni et al., On the calibration of multiclass classification with rejection, NeurIPS, 2019 (Theorem 7 (ฺBound for OVA loss based on strictly proper composite loss choice (square root rate for many losses according to Table 1)) and Theorem 8 (Bound for softmax cross-entropy loss (square root rate)).\n\n[4] Charoenphakdee et al., Classification with rejection based on cost-sensitive classification, ICML, 2021 (Theorem 8 (excess risk transfer bound for classification with rejection and general classification-calibrated loss) and Corollary 9 (Excess risk bound of hinge loss with linear rate)).\n\nBipartite ranking:\n\n[5] Gao and Zhou, On the consistency of AUC pairwise optimization, IJCAI, 2015 (Theorem 3 and Corollary 5, where Corollary 5 indicates that exponential and logistic losses give a square root regret bound).\n\n----- Updated comment after receiving the author feedback-----\n\nI have read other reviews and the author feedback. I appreciate the authors for the response.\n\nI found that the contributions of this paper are clear and useful as a general theory of polyhedral loss for any discrete target, that is, for any discrete target, there exists a polyhedral loss that has a linear regret transfer rate for it. In addition, this paper discusses a large class of loss functions (that is non-polyhedral but not exactly all possible non-polyhedral losses) that can always achieve a rate slower than linear. Both results are novel to the best of my knowledge and I think it is safe to say that this provides a solid understanding of polyhedral losses. While there exist several existing works that proved the regret transfer rate of a loss function (both polyhedral and non-polyhedral), it is usually done for a specific loss function, where the proof usually uses the specific property of that loss and it cannot be used for other losses. With the results of this submission, we can immediately use it for confirming the rate of convergence of a new loss function as long as it satisfies the condition (i.e., polyhedral or a class of non-polyhedral losses defined in this paper). Thus, it is quite clear that this paper is novel and useful and this is the main reason why I vote to accept this paper.\n\nOn weakness pointed out by other reviewers:\n\nAs we have seen in several existing works that polyhedral losses often (or always?) achieve the linear rate while it is not the case for many smooth losses, the result in this paper may not be very surprising. Nevertheless, I believe it is important to have a confirmation that this is indeed true in general. And it is nice to know that we can actually prove a general statement as suggested by the authors. Another weakness of this paper could be that there is no experiment. But I think this paper focuses on the theoretical perspective and it already has sufficient contribution for NeurIPS. The extensive empirical study can be done later as future work. Therefore, my score remains unchanged.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The discussion this paper provided is adequate.", "review_text": "", "extra_scores": {"ethical_concerns": "The discussion this paper provided is adequate.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10 hours"}, "extra_text": {}}, {"review_id": "BRylt_Z4f-_", "reviewer": "Reviewer_J1xj", "summary": "This paper shows the existence of linear regret bounds for polyhedral surrogates. While such bounds have been proven for specific surrogates this paper shows any calibrated linear surrogate has linear regret bounds. In addition it also shows any surrogate that is essentially not piecewise linear has only quadratic regret bounds, i.e. there exists distributions where target-regret >= sqrt(surrogate-regret).\n\n", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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 puts together several results in a convenient abstract form for future research. However, there is no surprise factor in any of the results. Both linear regret bounds for piecewise linear surrogates, and a quadratic lower bound for \"strongly-convex\" surrogates would not surprise researchers familiar with the area. The abstract proof techniques and definitions however are interesting and are the main contribution of the paper.\n\nOther comments:\n\n1. There are several properties whose implications are not clear. e.g. some of the properties are\nA. L is polyhedral.\nB. L,psi are consistent\nC L,psi are calibrated\nD. L,psi indirctly elicit l\nE. psi is epsilon separated w.r.t. Gamma\n\nFact 1 says B implies C imples D. But there are other implications that are missed. e.g. C also implies B. (Tewari et al. (2007), Ramaswamy 2016). I am also guessing A and D implies C. A figure illustrating all these properties using a block diagram would be useful.\n\n2. The polyhedral losses definition seems to exclude non-convex polyhedral losses. Is that on purpose?\n3. The separated link definition (informal version) seems wrong. e.g. with hinge loss surrogate and sign predictor for the binary zero-one loss, psi(0.001) is an optimal prediction but psi(-0.001) is not for some p but |0.001+0.001| is not greater than epsilon for this case.\n4. All these concepts would be better served by a more simple example, like the Crammer-Singer surrogate than the significantly more complex BEP surrogate. \n\n--- After rebuttal ---\n\nI thank the authors for their responses. I have read the other reviews and replies, and hence revise my score to 5 from 4. I still think a large portion of these results by themselves are not exciting/interesting. But this paper does provide the language and tools required for such results.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "5vq2rqkhwh-", "reviewer": "Reviewer_yteg", "summary": "The paper concerns theory of surrogate losses. The authors present general results concerning surrogate regret bounds which characterize how fast the target loss approaches the best possible solution if a surrogate loss is optimized. The authors point out that families of surrogate losses are characterized by different generalization rates (how fast the surrogate loss approaches optimum as a function of the number of training points) and regret transfer rates (how the surrogate regret translates to target regret). The authors focus on polyhedral losses (piecewise-linear convex loss functions; hinge loss is an examples of such function). Particularly, they show that the regret transfer for consistent polyhedral surrogates (a surrogate loss is consistent if its all optimal solutions are also optimal for the target loss) is linear (which is a desired rate). On the other hand, they show that for \"sufficiently non-polyhedral\" surrogates (like logistic loss) the transfer rate is no faster than a square root. Nevertheless, the generalization rate for smooth losses can be as fast as $\\frac{1}{n}$, while for polyhedral losses is $\\frac{1}{\\sqrt{n}}$. All together it leads to comparable surrogate regret rates.\n\n\n", "questions": "", "limitations": "", "rating": 6, "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": "This is a purely theoretical paper without any empirical evidence. It reads well, particularly the first part of the paper. It states and tries to answer an important question of regret rates for surrogate losses. \n\n### Originality\n\nThe question stated in the paper is one of the most important in theoretical machine learning. However, its practical implications can be of less importance as usually regret bounds are very loose. Nevertheless, they can serve as sanity checks and can be treated as guidelines for development of learning algorithms. The presented results nicely generalize previous findings. They are not so surprising, but give almost exhaustive picture of surrogate loss minimization. \n\n### Quality\n\nUnfortunately, I was not able to check the appendix. Nevertheless, the theoretical results sound plausible. However, the paper has several drawbacks that decrease its final evaluation:\n\n- It is not clear what is the final goal of the paper. I suppose that the authors aim at comparing polyhedral and smooth surrogate losses. Unfortunately, I am missing examples of bounds for a variety of problems for both types of losses. An experimental comparison would also be desired, as authors write that the results will be useful for practitioners. \n\n- It is also not clear to what machine learning problems the results apply. It is clear that for binary classification under 0/1 and abstain loss. But what are the other problems? The authors say that one can construct consistent polyhedral surrogates for any discrete target loss. But this general sentence is hiding important message for practitioners. The results in [8] show that there are important practical problems for which polyhedral losses are inconsistent and therefore the presented findings in this paper do not apply to. An example of such problem is top-$k$ classification. The paper should discuss in more detail what usual problems are \"positive\" and \"negative\" instances of the presented theory. \n\n### Clarity\n\nThis is a purely theoretical paper, but the authors made an effort to make it easy to follow, especially the first part. The second part is much more dense (because of the page limit) therefore requires much more time to go through. To improve clarity, I would encourage authors to give more examples of problems and losses to which the theory applies. Also, a comparison of the bounds for polyhedral and smooth surrogates would make the final message much clearer.\n\nMinor comments concerning clarify are given below:\n\n- Weak optimality: What is the meaning of \"weak optimal\" in the considered case? This statement appears twice in the paper, but there is no definition or interpretation of it given. \n\n- Link function: How often the name link function is used in this context? In statistics, link function has a very precise definition. There is some analogy to the context used by the authors, but a different name such as prediction or inference function would probably sound better and less confusing. Let us consider binary classification and logistic regression for which we have: real scoring function, link function that maps real values to probabilities, and finally prediction function that translates probabilities to binary predictions. The other names are also commonly used in multi-label classification or structured-output prediction where procedures of translating surrogate scoring functions to final predictions are usually quite complex.\n\n### Significance:\n\nIn general, the results given in the paper are of high importance for theory of machine learning. Nevertheless, the significance is decreased by the lack of the final comparison between polyhedral and smooth losses and detailed discuss about the problems to which the theory does and does not apply.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper advances understanding of learning theory. There are no negative societal impacts.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper shows that every consistent polyhedral surrogate loss has a linear surrogate regret bound, while if the loss is sufficiently non-polyhedral (strongly convex) the regret bound is a square root (fast surrogate generalization rates translate to slow rates).

The reviewers liked the generality of these results and most of them believe this is a solid contribution to a general theory of surrogate losses. The technical part of the paper is sound. Clearly, the paper answers an interesting open question.

While I recommend the paper for acceptance, I still have two concerns:
- The results are based on the definition of the regret as the suboptimality with respect to the optimal prediction function **among all functions**, rather than optimal **within some class of functions** (e.g., linear). So these results are only useful if the learning method is able to converge to the optimal predictor at all (i.e. either the optimal is within the class of functions the method works with, or the method is universal). I guess this criticism applies to a general research topic on the consistency of surrogate losses rather than specifically to this particular paper.
- While having linear regret transfer is definitely nice, losses without curvature (polyhedral) generally suffer from the slow rates of convergence (w.r.t. sample size) $O(1/\sqrt{n})$ in the worst case, while strongly convex losses have fast rates $O(1/n)$. So after all, it is not clear which losses work best.
Decision: Accept (Poster)