Surrogate Regret Bounds for Polyhedral Losses
Year: 2022

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.

heading: 1 Introduction
text: In supervised learning, our goal is to learn a hypothesis that solves some target problem given labeled data. The problem is often specified by a 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 ` over a data set is typically NP-hard, we instead turn to the general paradigm of surrogate risk minimization. Here a surrogate loss function L is chosen and minimized instead of the target `. A link function ψ then maps the surrogate predictions to target predictions.
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 at 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 a hypothesis to be its performance relative to the Bayes optimal hypothesis, we wish to know how quickly the `-regret approaches zero.
Surrogate regret bounds are a common tool to prove generalization rates for surrogate risk minimization, 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, a surrogate regret bound takes the form
∀ surrogate hypotheses h, Regret`(ψ ◦ h) ≤ ζ( RegretL(h) ) , (1)
where the regret transfer function ζ : R+ → R+ controls how surrogate regret translates to target regret. For example, if we have a sequence of surrogate hypotheses hn achieving a fast rate RegretL(hn) = O(1/n), and we have a regret transfer of ζ( ) = √ , then we can only guarantee a
slower target rate of Regret`(ψ◦hn) = O(1/ √ n). The ideal regret transfer is linear, i.e. ζ( ) = C · for some C > 0, which would have directly translated the fast-rate guarantee to the target.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Much is known about surrogate regret bounds for particular problems, especially for binary classification 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-linear and convex) surrogate, like hinge loss, or a smooth surrogate like exponential or squared loss. The surrogate rate for polyhedral losses will likely be a slower O(1/ √ n), whereas a faster O(1/n) rate is typical for smooth surrogates—but what is the tradeoff when it comes to the regret transfer function ζ, 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 a constant factor.
Theorem 1 (Linear bound for polyhedral). Let L be any polyhedral surrogate and ψ any link function such that (L,ψ) is consistent for the target loss `. Then L satisfies Equation 1 with a linear ζ.
The recent embedding framework of Finocchiaro et al. [10] shows how to 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 a consistent surrogate for some discrete target. Theorem 1 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.1
We also give a partial converse: If the surrogate is sufficiently “non-polyhedral”, i.e. 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-polyhedral”). Let L be a locally strongly convex surrogate with locally Lipschitz gradient. If L satisfies Equation 1 for a target loss `, then there exists c > 0 such that, for all small enough ≥ 0, we have ζ( ) ≥ c · √ .
While it may seem intuitive that ζ = √ · for strongly convex losses, it is well-known that losses like exponential loss for binary classification also have ζ = √ ·, even though they are neither strongly convex nor strongly smooth [4]. Theorem 2 offers an explanation for this phenomenon, and together with Theorem 1 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 O(1/ √ n) will translate to the target unchanged, while most smooth surrogates, even if achieving a fast surrogate generalization rate of O(1/n), will likely yield the same target rate of O(1/ √ n). Our results therefore suggest an inherent tradeoff fast surrogate rates and optimal regret transfer, a 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 a polyhedral loss can be bounded by ζ(t) ≤ α · t where the constant is of the form α = α` · αL · αψ . Each component of α depends only on its respective object `, L, and ψ. A corollary of the derivation is that a polyhedral loss L and link ψ are consistent for ` if and only if ψ is -separated, a condition introduced in Finocchiaro et al. [10].

heading: 1.1 Literature on surrogate regret bounds
text: 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.
1Many of these polyhedral surrogates mentioned are actually known to 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 a 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 classification [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 an 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 a quadratic surrogate, for a 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-Vila et al. [20, Theorem 4.4] give even more general bounds, using a broader class of surrogates based on estimating a vector-valued expectation. All of these works apply to a 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-Vila et al. [20, Theorem 4.5] also provide lower bounds, in the same spirit as our Theorem 2 but only for the classes of surrogates they study. In particular, our results recover their bounds up to a 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 0. 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 a 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 on the data, 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.

heading: 2 Preliminaries
text: Target problems. We consider supervised machine learning problems where data points have features in X and labels in Y , a finite set. The target problem is to learn a hypothesis mapping X to a report (or prediction) spaceR, possibly different from Y . For example, binary classification has Y = R = {−1,+1}, whereas for ranking problemsR may be the set of permutations of Y . In this paper, we assume R is a finite set. The target problem is specified by the target loss ` : R → RY+, which maps a report (prediction) r ∈ R to the vector `(r) of nonnegative loss values for each label,
2These works express surrogate regret bounds with ζ−1 appearing on the left-hand side of eq. (1), and thus the terms “upper bound” and “lower bound” are reversed from their terminology.
i.e. `(r) = (`(r)y)y∈Y . Given a hypothesis g : X → R and a data point (x, y) ∈ X × Y , the loss is `(g(x))y . We make a minimal non-redundancy assumption on `, formalized in Section 2.1. We may refer to ` as a discrete target loss to emphasize our assumption thatR and Y are finite.
Surrogate problems. We recall the surrogate risk minimization framework. First, one constructs a surrogate loss function L : Rd → RY+. Then, one minimizes it to learn a hypothesis of the form h : X → Rd. Finally, one applies a link function ψ : Rd → R, which maps h to the implied target hypothesis ψ ◦ h.3 In other words, if a surrogate prediction h(x) ∈ Rd implies a prediction ψ(h(x)) ∈ R for the target problem. For example, in binary classification, the target problem is given by 0-1 loss, `zo(r)y = 1{r 6= y}, with surrogate losses typically defined over R. Common surrogate losses for 0-1 loss include hinge loss Lhinge(u)y = max(1 − uy, 0), logistic loss Llog(u)y = ln (1 + exp(−yu)), and exponential loss Lexp(u)y = exp(−yu). These surrogates are typically associated with the link ψ : u 7→ sign(u), which maps negative predictions to −1 and nonnegative predictions to +1, breaking ties arbitrarily at 0.
Surrogate regret bounds. The suitability and efficiency of a chosen surrogate is often quantified with a surrogate regret bound. Formally, the surrogate regret of h with respect to data distribution D is given by RL(h;D) = E(X,Y )∼D L(h(X))Y − infh′:X→Rd E(X,Y )∼D L(h′(X))Y , 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 target regret of the implied hypothesis ψ ◦ h is R`(ψ ◦ h;D) = E(X,Y )∼D `(ψ(h(X)))Y − infh′:X→R E(X,Y )∼D `(h′(X))Y , where we recall that ψ is the link function.
A surrogate regret bound answers the following question: when we minimize the surrogate regret at a rate f(n), given n data points, how fast does the target regret diminish? Formally, we say that ζ : R+ → R+ is a regret transfer function if ζ is continuous at 0 and satisfies ζ(0) = 0. Given a rerget transfer function ζ, we say that (L,ψ) guarantees a regret transfer of ζ for ` if
∀D,∀h : X → Rd, R`(ψ ◦ h;D) ≤ ζ(RL(h;D) ) . (2) We note that a classic minimal requirement for (L,ψ) is that they be consistent for `, which is the case if there exists any regret transfer ζ guaranteed by (L,ψ) for ` [29]. In other words, consistency implies that RL(h;D)→ 0 =⇒ R`(ψ ◦ h;D)→ 0, but says nothing about the relative rates.
Polyhedral surrogates. A function f : Rd → R is called polyhedral if it can be written as a pointwise maximum of a finite set of affine functions [27, § 19]. The epigraph of a polyhedral function is a polyhedral set, i.e. the intersection of a finite set of closed halfspaces; thus polyhedral functions are always convex. We say a surrogate loss L : Rd → RY+ is polyhedral if, for each fixed y ∈ Y , the loss as a function of prediction, i.e. r 7→ L(r)y , is polyhedral.

heading: 2.1 Property elicitation and the conditional approach
text: Our technical approach is based on property elicitation, which studies the structure of ` and L as they relate to ∆Y . This involves a conditional perspective. Given a data distribution D on X × Y , for (X,Y ) ∼ D, we consider the format of possible target predictions g(x) = r ∈ R; surrogate predictions h(x) = u ∈ Rd; and conditional distributions Pr[· | X] = p ∈ ∆Y . By dropping the role of the hypotheses and the feature space X , we can focus on the relationships of the functions `(r)y and L(u)y and the conditional distribution p.
In particular, in our notation the expected L-loss of prediction u on distribution p is simply the inner product 〈p, L(u)〉. The Bayes risk of L is L(p) = infu∈Rd〈p, L(u)〉, and similarly the Bayes risk of ` is `(p) = infr∈R〈p, `(r)〉. We abuse notation to define the conditional surrogate regret RL(u, p) = 〈p, L(u)〉−L(p), and similarly the conditional target regret R`(r, p) = 〈p, `(r)〉− `(p). Given a regret transfer function ζ , we say (L,ψ) guarantees a conditional regret transfer of ζ for ` if, for all p ∈ ∆Y and all u ∈ Rd, R`(ψ(u), p) ≤ ζ(RL(u, p)). The following is a direct result of Jensen’s inequality, using that RL(h;D) = EX RL(h(X), pX) where pX is the conditional distribution on Y given X .
3The term “link function” can carry a more specific 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 a valid link function, though perhaps not a calibrated one.
Observation 1. If (L,ψ) guarantee a conditional regret transfer of ζ for `, and ζ is concave, then (L,ψ) guarantee a regret transfer of ζ for `.
Property elicitation. To begin, we define a property, which is essentially a statistic or summary of a distribution, such as the mode. We then define what it means for a loss function to elicit a property. We write Γ : ∆Y ⇒ R as shorthand for Γ : ∆Y → 2R \ {∅}. Definition 1 (Property, level set). A property is a function Γ : ∆Y ⇒ R, for some set R. The level set of Γ for report r is the set Γr = {p ∈ ∆Y : r ∈ Γ(p)}.
The following definition applies both to target losses and surrogate losses.
Definition 2 (Elicits, report space). A loss function f : R→ RY+, where the domain R is called the report space, elicits a property Γ : ∆Y ⇒ R if
∀p ∈ ∆Y , Γ(p) = arg min r∈R 〈p, f(r)〉 =: prop[f ](p) . (3)
As each loss f elicits a unique property, we refer to it as prop[f ]. In particular, we will consistently use the notation Γ = prop[L] where L is a surrogate loss with report space Rd, and we will use γ = prop[`] where ` is a target loss with finite report spaceR. For example, prop[`zo] is simply the mode of p, given by mode(p) = {−1, 1} if 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 ∈ R are possibly uniquely optimal. Formally, letting γ = prop[`], we suppose that for all r ∈ R, there exists p ∈ ∆Y with γ(p) = {r}.4
Calibration and consistency. It is known that consistency implies the weaker condition of calibration, which implies the still-weaker, but very useful, condition of indirect elicitation. To define these conditions, consider L,ψ, ` and γ = prop[`]. Recall that γ(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: a surrogate-link pair (L,ψ) indirectly elicits γ if u ∈ prop[L](p) =⇒ ψ(u) ∈ γ(p) for all p ∈ ∆Y . Note that if ψ(u) 6∈ γ(p), then u is a “bad” (suboptimal) surrogate prediction for p. Let BL,ψ,`(p) = {RL(u, p) : ψ(u) 6∈ γ(p)}, 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 a nonzero gap between the expected loss of a “good” report and that of any bad one. Definition 3 (Indirectly Elicits, Calibrated). Let ` be a target loss and γ = prop[`]. A surrogate-link pair (L,ψ) indirectly elicits γ if 0 6∈ BL,ψ,`(p) for all p ∈ ∆Y . The pair (L,ψ) is calibrated for ` if 0 < inf BL,ψ,`(p) for all p ∈ ∆Y . Fact 1 ([4, 29]). Let ` : R → RY+ be a target loss with finite R and Y . If a surrogate and link (L,ψ) are consistent for `, then (L,ψ) are calibrated for L. If (L,ψ) are calibrated for `, then they indirectly elicit `.
For example, it is well-known that hinge loss Lhinge is calibrated and consistent for 0-1 loss `zo using the link ψ : u 7→ sign(u). Recall that `zo elicits the mode. One can verify that indeed (Lhinge, ψ) indirectly elicit the mode; for example, BLhinge,ψ,`zo(0) = BLhinge,ψ,`zo(1) = [1,∞) and BLhinge,ψ,`zo(1/2) = ∅, neither of which contain 0.

heading: 3 Upper Bound: Polyhedral Surrogates
text: 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 ∈ ∆Y . Prove a regret bound for this fixed p, namely a constant αp such that R`(ψ(u), p) ≤ αpRL(u, p) for all u ∈ Rd.
2. Apply this regret bound to each p in a carefully chosen finite subset of ∆Y . Argue that the maximum αp from this finite set suffices for the overal regret bound.
4Technically, this definition differs from the one given in literature [10, 11], but the two are equivalent for finite elicitable properties.
The first part will actually hold for any calibrated surrogate. The second part relies on a crucial fact about polyhedral losses L: their properties Γ = prop[L] cover the whole simplex with only a finite number of polyhedral level sets [10]. Thus, although the prediction space Rd is infinite, one can restrict to just a finite set of prediction points and always have a global minimizer of expected surrogate loss.

heading: 3.1 Linear transfer for fixed p
text: First, we establish a linear transfer function for any fixed conditional distribution p. This statement holds for any calibrated surrogate, not necessarily polyhedral.
Lemma 1. Let ` : R → RY+ be a discrete target loss and suppose the surrogate L : Rd → RY+ and link ψ : Rd → R are calibrated for `. Then for any p ∈ ∆Y , there exists αp ≥ 0 such that, for all u ∈ Rd,
R`(ψ(u), p) ≤ αpRL(u, p).
While useful, this result is somewhat nonconstructive and potentially loose. In Section 5, we unpack the constant αp for polyhedral losses in particular.

heading: 3.2 Linear overall transfer function
text: Given Lemma 1, we might hope to obtain that, for any calibrated surrogate, there exists α = supp αp such that R`(ψ(u), p′) ≤ αRL(u, p′) for all p′. However, we know this is false in general: not all surrogates yield linear regret transfers! Indeed, for many surrogates, the supremum will be +∞. However, polyhedral surrogates have a special structure that allows us to show α is finite. We first present some tools that hold for general surrogates, then the key implication from L being polyhedral. Lemma 2 ([12]). If (L,ψ) indirectly elicits γ, then Γ = prop[L] refines γ in the sense that, for all u ∈ Rd, there exists r ∈ R such that Γu ⊆ γr.
The next lemma states that surrogate regret is linear in p on any fixed level set Γu∗ 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,ψ) indirectly elicits γ = prop[`] and let Γ = prop[L]. Then for any fixed u, u∗ ∈ Rd and r ∈ R, the functions RL(u, ·) and R`(r, ·) are linear on Γu∗ in their second arguments.
A key fact we use about polyhedral losses is that they have a finite set of optimal sets.
Lemma 4. If L : Rd → RY+ is polyhedral, then Γ = prop[L] has a finite set of level sets that union to ∆Y . Moreover, these level sets are polytopes.
We are now ready to restate the main upper bound and sketch a proof.
Theorem 3 (Theorem 1 restated). Suppose the surrogate loss L : Rd → RY+ and link ψ : Rd → R are consistent for the target loss ` : R → RY+. If L is polyhedral, then (L,ψ) guarantee a linear regret transfer for `, i.e. there exists α ≥ 0 such that, for all D and all measurable h : X → Rd,
R`(ψ ◦ h;D) ≤ αRL(h;D).
The key point of the proof is that, by Lemma 4, the polyhedral loss L has a finite set U ⊂ Rd of predictions such that (a) for each u ∈ U , the level set Γu is a polytope, and (b) ∪u∈UΓu = ∆Y . Let Q be the finite set of all vertices of all these level sets. For any vertex q ∈ Q, we have a linear regret transfer for this fixed q with constant αq from Lemma 1. Lemma 3 allows us to write the regret of a general p as a convex combination of the regrets of its containing level set’s vertices. So we obtain a bound of α = maxq∈Q αq .

heading: 4 Lower bound
text: In this section, we show that if a surrogate loss is sufficiently “non-polyhedral”, then the best regret transfer it can achieve is ζ( ) on the order of √ . (Proofs are deferred to Appendix B.) Specifically, we consider a relaxation of L being both strongly smooth and strongly convex, as we now formalize.
Let Γ = prop[L] and γ = prop[`]. We will assume L is strongly smooth everywhere and strongly convex around some boundary report for L, `, which we define to be a u0 ∈ Rd such that, for some r, r′ ∈ R, there exists a distribution p0 such that p0 ∈ Γu0 ∩ γr ∩ γr′ . For the conditional distribution p0, the surrogate report u0 minimizes expected L-loss, and it may link to either r or r′, as either of these minimize expected `-loss. Recall that an open neighborhood of u0 is an open set in Rd containing u0. Assumption 1. L : Rd → RY+ is a surrogate and ψ : Rd → R a link, consistent with the discrete target ` : R → RY+, satisfying the following: (i) For all y ∈ Y , the function L(·)y is differentiable with a locally Lipschitz gradient.5 (ii) For some α > 0 and some boundary report u0 ∈ Rd for L, `, the expected loss function u 7→ 〈p, L(u)〉 is α-strongly convex on an open neighborhood of u0.
This assumption is quite weak. In particular, because ` has a finite report set R, boundary reports essentially always exist whenever (L,ψ) indirectly elicits `. In particular, as the level sets of γ are closed, convex, and union to the simplex [10, 15], there must be some pair of reports r, r′ ∈ R with γr ∩ γr′ 6= ∅. We can then take p0 ∈ γr ∩ γr′ , and any u0 ∈ Γ(p0). One caveat is that we may have Γ(p0) = ∅. While some surrogates may fail to have a 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 Lexp(u)y = exp(−uy), where prop[Lexp](0) = prop[Lexp](1) = ∅, but we still have prop[Lexp](1/2) = {0}. The following result is our main lower bound. Theorem 4 (Stronger version of Theorem 2.). Suppose the surrogate loss L and link ψ satisfy a regret transfer of ζ for a target loss `. If L, ψ, and ` satisfy Assumption 1, then there exists c > 0 such that, for some ∗ > 0, for all 0 ≤ < ∗, ζ( ) ≥ c √ .
The key idea of the proof is to fix a boundary report u0 and consider a sequence of distributions pλ → p0 as λ→ 0. Target regretR`(ψ(u0), pλ) shrinks linearly in λ, but surrogate regretRL(u0, pλ) shrinks quadratically. The latter holds roughly because expected surrogate loss is strongly convex in some neighborhood of u0 and is strongly smooth elsewhere.6
Theorem 4 captures a wide range of surrogate losses beyond those that are strongly convex and strongly smooth. For example, exponential loss Lexp(u)y = exp(−uy) is not strongly convex, but does satisfy Assumption 1; for part (ii), the boundary report is u0 = 0 as we saw above, and Lexp is 1/e-strongly convex on (−1, 1) 3 u0. As another example, consider Huber loss for binary classification. Here Y = {±1} and the prediction space is R, and Huber loss can be defined by letting the hinge loss be t = max{0, 1 − ry} and setting L(r)y = t2 if t ≤ 2, else 4(t− 1). Theorem 4 does capture Huber, but needs the strength of Assumption 1(ii) as Huber is strongly convex on [−1, 1] but linear outside that interval.

heading: 5 Unpacking the constant for polyhedral losses
text: Our main upper bound for polyhedral losses, Theorem 1, is mostly nonconstructive: it says polyhedral surrogates have some α such that R`(ψ ◦ h;D) ≤ α ·RL(h;D). In this section, we make the result constructive by unpacking the implications of consistency for polyhedral surrogates. Proofs appear in Appendix C.

heading: 5.1 Contribution from the target, surrogate, and link
text: We will give a bound on the constant of the form α ≤ α` · αL · αψ , i.e. one component each relating to the structure of the target loss, surrogate loss, and link. First, we will derive αL using the theory of Hoffman constants from linear optimization [14]. Then, we will show that any link for a consistent polyhedral loss must satisfy a condition called -separation, introduced in [10]. We will set αψ = 1 . With α` simply an upper bound on the target loss, we will finally prove α ≤ α` · αL · αψ .
5A map g : A→ B is locally Lipschitz if for every a ∈ A there is an open neighborhood U of a such that g|A is Lipschitz continuous.
6A tempting alternative is to fix a distribution p0 and consider a sequence of predictions. We know from Lemma 1 that this approach will fail, however: for any consistent surrogate and any fixed p0, there is a linear regret transfer if we restrict to p0.

heading: 5.1.1 Hoffman constants
text: The intuition we explore here is the linear growth rate of a given polyhedral function as we move away from its optimal set. In particular, consider the expected loss u 7→ 〈p, L(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 ([14]). Let L : Rd → RY+ be a polyhedral loss with Γ = prop[L]. Then for any fixed p, there exists some smallest constant HL,p ≥ 0 such that d∞(u,Γ(p)) ≤ HL,pRL(u, p) for all u ∈ Rd.
To foreshadow the usefulness of HL,p, recall the proof strategy of the upper bound: use Lemma 1 to obtain a constant αp for each p; then carefully choose a finite set of p’s and take the maximum constant. In the same way, we will be able to set the “loss” constant αL = maxpHL,p. First, however, we will need to investigate separated links.

heading: 5.1.2 Separated link functions
text: A link is -separated if, for all pairs of surrogate reports u, u∗ such that u∗ is optimal for the surrogate and u links to a suboptimal target report, we have ‖u∗ − u‖∞ > . The definition was introduced by Finocchiaro et al. [10]. Definition 4 (Separated Link). Let properties Γ : ∆Y ⇒ Rd and γ : ∆Y ⇒ R be given. We say a link ψ : Rd → R is -separated with respect to Γ and γ if for all u ∈ Rd with ψ(u) /∈ γ(p), we have d∞(u,Γ(p)) > , where d∞(u,A) . = infa∈A ‖u − a‖∞. Similarly, we say ψ is -separated with respect to L and ` if it is -separated with respect to prop[L] and prop[`].
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, -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 a polyhedral loss have an associated -separated link?
Finocchiaro et al. [10] showed that -separated links for polyhedral surrogates are calibrated. We show that the converse is in fact true: every calibrated link is -separated for some > 0. The proof follows a similar argument to that of Tewari and Bartlett [30, Lemma 6].
Lemma 6. Let polyhedral surrogate L : Rd → RY+, discrete loss ` : R → RY+, and link ψ : Rd → R be given such that (L,ψ) is calibrated with respect to `. Then there exists > 0 such that ψ is -separated with respect to Γ .= prop[L] and γ .= prop[`].

heading: 5.1.3 Combining the loss and link
text: 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 ( ψ). If (L,ψ) are calibrated for `, then let ψ . = sup{ : ψ is -separated}.
We will also need an upper bound C` = maxr,pR`(r, p) on the regret of `. Since R` is convex in p, in particular this maximum is achieved at a vertex of the probability simplex.
Definition 6 (C`). Given discrete loss ` : R → RY+, define C` = maxr,r′∈R,y∈Y `(r)y − `(r′)y .
Recall that Lemma 4 gave that, ifL is polyhedral, then Γ = prop[L] has a finite set of full-dimensional level sets, each a polytope, that union to the simplex.
Definition 7 (HL). Given a polyhedral surrogate loss L : Rd → RY+, let Q be the set of all vertices of the full-dimensional level sets of Γ = prop[L], and define HL . = maxp∈QHL,p.
Theorem 5 (Constructive linear transfer). Let ` : R → RY+ be a discrete target loss, L : Rd → RY+ be a polyhedral surrogate loss, and ψ : Rd → R a link function. If (L,ψ) are consistent for `, then
(∀h,D) R`(ψ ◦ h;D) ≤ C`HL ψ RL(h;D) .
The proof closely mirrors the proof of the nonconstructive upper bound, Theorem 1, but using the constructive constants C`, HL, ψ derived above. To summarize, we have shown the following.
Theorem 6. Let ` : R → RY+ be a discrete target loss, L : Rd → RY+ be a polyhedral surrogate loss, and ψ : Rd → R a link function. The following are equivalent:
1. (L,ψ) is consistent for `.
2. ψ is -separated with respect to L and ` for some > 0.
3. (L,ψ) guarantees a linear regret transfer for `.
Furthermore, if any of the above hold, then in particular (L,ψ) guarantees the regret transfer ζ(t) = ( C`HL ψ ) t.

heading: 5.2 Further tightening
text: While our goal is not to focus on exact constants for specific problems, we remark on a few ways Theorem 5 may be loose and how one could compute the tightest possible constant α∗ for which R`(ψ ◦h;D) ≤ α∗RL(h;D) for all h andD. In general, for a fixed p, there is some smallest α∗p such that R`(ψ(u), p) ≤ α∗pRL(u, p) for all u. Then, it follows from our results that α∗ = maxp∈Q α∗p for the finite set Q used in the proof, i.e. the vertices of the full-dimensional level sets of Γ = prop[L].
Above, we bounded α∗p ≤ C`HL,p ψ . The intuition is that some u at distance ≥ ψ from Γ(p), the optimal set, may link to a “bad” report r = ψ(u) 6∈ γ(p). The rate at which L grows is at least HL,p, so the surrogate loss at u may be as small as
ψ HL,p , while the target regret may be as high as
C` = maxr′,p′ R`(r ′, p′). The ratio of regrets is therefore bounded by HL,pC` ψ .
The tightest possible bound, on the other hand, is α∗ = supu:ψ(u)6∈γ(p) R`(ψ(u),p) RL(u,p) . This bound can be smaller if the values of numerator and denominator are correlated across u. For example, u may only be ψ-close to the optimal set when it links to reports ψ(u) with lower target regret; or L may have a smaller slope in the direction where the link’s separation is larger than .
To illustrate with a concrete example, consider the binary encoded predictions (BEP) surrogate of [25] for the abstain target loss, `(r, y) = 12 if r = ⊥, otherwise `(r, y) = 1[r 6= y]. The surrogate involves an injective map B : Y → {−1, 1}d for d = dlog2 |Y|e. It is L(u)y = maxj=1...d(1− udB(y)d)+, where (·)+ indicates taking the maximum of the argument and zero. The associated link is ψ(u) = ⊥ if minj=1...d |uj | ≤ 12 , otherwise ψ(u) = arg miny∈Y ‖B(y)− u‖∞.
One can show that for p = δy, i.e. the distribution with full support on some y ∈ Y , L(u)y = d∞(u,Γ(p)) exactly, givingHL,p = 1. It is almost immediate that ψ = 12 . Meanwhile,R`(r, p) ≤ 1, giving us an upper bound α∗p ≤ (1)(1) 1/2 = 2. In fact, this is slightly loose; the exact constant, given in [25] is 1. The looseness stems from the fact that for p = δy, the closest reports u to the optimal set, i.e. at distance only ψ = 12 away, do not link to reports maximizing target regret; they link to the abstain report ⊥, which has regret only 12 . With this correction, and an observation that all u linking to reports y′ 6= y are at distance at least 32 from Γ(p), we restore the tight bound α ∗ p ≤ 1. A similar but slightly more involved calculation can be carried out for the other vertices p ∈ Q, which turn out to be all vertices of the form 12δy + 1 2δy′ .
Finally, while we use ‖ · ‖∞ to define the minimum-slope HL and the separation ψ, in principle one could use another norm. One reason for restricting to ‖ · ‖∞ 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 HL and ψ in ‖ · ‖∞ imply existence of constants for other norms. These constants may change for different norms, and in particular, the optimal overall constant may arise from a norm other than ‖ · ‖∞.

heading: 6 Discussion
text: We have shown two broad results about regret tranfer functions for surrogate losses. In particular, polyhedral surrogates always achieve a linear transfer, whereas “non-polyhedral” surrogates are generally square root. Section 5 outlines several directions to further refine the bound for polyhedral surrogates. Beyond these directions, an 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 we study. In particular, Lemma 4 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, we 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 a theoretical work, the likely impacts of this paper take the form of downstream research and applications. Instead of direct applications, we 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-2045347.

Review summaries:
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).  

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). 

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.