# An Embedding Framework for the Design and Analysis of Consistent Polyhedral
Surrogates

Jessie Finocchiaro
<EMAIL_ADDRESS>Rafael Frongillo
<EMAIL_ADDRESS>Bo Waggoner
<EMAIL_ADDRESS>
( University of Colorado Boulder
)

###### Abstract

We formalize and study the natural approach of designing convex surrogate loss
functions via embeddings, for problems such as classification, ranking, or
structured prediction. In this approach, one embeds each of the finitely many
predictions (e.g. rankings) as a point in $\mathbb{R}^{d}$, assigns the
original loss values to these points, and “convexifies” the loss in some way
to obtain a surrogate. We establish a strong connection between this approach
and polyhedral (piecewise-linear convex) surrogate losses: every discrete loss
is embedded by some polyhedral loss, and every polyhedral loss embeds some
discrete loss. Moreover, an embedding gives rise to a consistent link function
as well as linear surrogate regret bounds. Our results are constructive, as we
illustrate with several examples. In particular, our framework gives succinct
proofs of consistency or inconsistency for various polyhedral surrogates in
the literature, and for inconsistent surrogates, it further reveals the
discrete losses for which these surrogates are consistent. We go on to show
additional structure of embeddings, such as the equivalence of embedding and
matching Bayes risks, and the equivalence of various notions of non-redudancy.
Using these results, we establish that indirect elicitation, a necessary
condition for consistency, is also sufficient when working with polyhedral
surrogates.

##  1 Introduction

In supervised learning, one tries to learn a hypothesis which fits labeled
data as judged by a target loss function. Minimizing the target loss directly
is typically computationally intractable for discrete prediction tasks like
classification, ranking, and structured prediction. Instead, one typically
minimizes a surrogate loss which is convex and therefore efficiently
minimized. After learning a surrogate hypothesis, a link function then
translates back to the target problem. To ensure the surrogate and link
properly correspond to the target problem, the surrogate must be _consistent_
, meaning that minimizing the surrogate loss over enough data will also
minimize the target loss.

While a growing body of work seeks to design and analyze consistent convex
surrogates for particular target loss functions, to date much of this work has
been ad-hoc. We lack general tools to systematically construct consistent
convex surrogates, much less an understanding of the full class of consistent
surrogates. For example, in multiclass and top-$k$ classification, several
proposed surrogates were proposed and adopted but later proved to be
inconsistent [59, 11, 49]. This state of affairs is even more dire for
structured prediction, where in addition to convexity and consistency, one
often requires a low _prediction dimension_ (the dimension of the surrogate
prediction space) as the label set can grow exponentially large. Clever
constructions like the binary-encoded predictions (BEP) surrogate for
multiclass classification with an abstain option [44], which achieves
logarithmic prediction dimension, are the exception rather than the rule. In
all of these settings, we lack a unifying framework that moves from a given
target problem to a convex consistent surrogate and link function.

To address this shortcoming, we introduce a new framework motivated by a
particularly natural approach for finding convex surrogates, wherein one
“embeds” a discrete loss. Specifically, we say a convex surrogate $L$ embeds a
discrete target loss $\ell$ if there is an injective embedding from the
discrete reports (predictions) to $\mathbb{R}^{d}$ such that (i) the original
loss values are recovered, and (ii) a report is $\ell$-optimal if and only if
the embedded report is $L$-optimal. (See § 2.4.) Common examples of this
general construction include hinge loss as a surrogate for 0-1 loss and the
BEP surrogate mentioned above [44].

Using this framework, we give several constructive results to design new
consistent surrogates, as well as a suite of tools to analyze existing
surrogates. As a first step, in § 3, we show that such an embedding scheme is
intimately related to the class of _polyhedral_ loss functions, i.e., those
that are piecewise-linear and convex.

######  Theorem 1.

Every discrete loss $\ell$ is embedded by some polyhedral loss $L$, and every
polyhedral loss $L$ embeds some discrete loss $\ell$.

Crucially, we go on in § 4 to show that an embedding gives rise to a
calibrated link function, and is therefore consistent with respect to the
target loss.

######  Theorem 2.

Given any polyhedral loss $L$, let $\ell$ be a discrete loss it embeds. There
exists a link function $\psi$ such that $(L,\psi)$ is calibrated with respect
to $\ell$.

Beyond consistency, we show in § 4.3 that any polyhedral surrogate achieves a
linear surrogate regret bound, which allows one to translate generalization
bounds from the surrogate to the target. Our results are constructive: given a
discrete target loss, we show how to define a surrogate and construct a
calibrated link, and given a polyhedral surrogate, we show how to find a
discrete loss that it embeds.

We demonstrate the constructiveness of our framework in § 5 with several
applications, many of which are subsequent to our work. In addition to
constructing new surrogates, we illustrate the power of our framework to
analyze previously proposed polyhedral surrogates. For example, while we know
that the inconsistent top-$k$ polyhedral surrogates mentioned above do not
solve top-$k$ classification, our framework illuminates the problem they _do_
solve, and what restrictions on the underlying distribution would render them
top-$k$ consistent (§ 5.5).

Underpinning our results are several observations, outlined in § 6, which
formalize the idea that polyhedral losses “behave like” discrete losses. In
particular, any polyhedral loss $L$ has a finite _representative set_
$\mathcal{S}$ of reports, such that for all distributions, some report in
$\mathcal{S}$ is $L$-optimal. We show that $L$ embeds the discrete loss
$\ell=L|_{\mathcal{S}}$ given by restricting $L$ to just the reports in
$\mathcal{S}$. To go from a discrete loss to a polyhedral surrogate, we prove
that the conditions of an embedding are equivalent to matching Bayes risks
(Proposition 2), and use the fact that discrete losses and polyhedral losses
both have polyhedral Bayes risks.

Finally, we also provide several observations beyond what is needed to prove
our main results, which we view as conceptual contributions (§ 6, 7). Using
tools from property elicitation, we show an equivalence between minimum
representative sets (those of minimum cardinality) and “non-redundancy”,
wherein no report is dominated by another. We further show that, while a
minimum representative set is not always unique, the loss values associated
with it are unique, giving rise to a natural “trim” operation on losses. The
paper concludes with an interesting observation (Theorem 8): while indirect
property elicitation is generally a strictly weaker condition than
consistency, the two are equivalent when restricting to the class of
polyhedral surrogates.

Taken together, we view our contributions as both conceptual and practical. We
uncover the remarkable structure of polyhedral surrogates, deepening our
understanding of the relationship between surrogate and discrete target
losses. This structure leads to a powerful new framework to design and analyze
surrogate losses. As we illustrate with several examples, this framework has
already been applied to solve open questions by designing new surrogates, to
uncover the behavior of existing surrogates, and to construct link functions
in complex structured problems. We conclude with several directions for future
work.

##  2 Setting

For discrete prediction problems like classification, the given (discrete)
loss is often computationally intractable to optimize directly. Therefore,
many machine learning algorithms instead minimize a surrogate loss function
with better optimization qualities, such as convexity. To ensure that this
surrogate loss successfully addresses the original target problem, one needs
to establish statistical consistency, a minimal requirement that is a
prerequisite for generalization bounds. Consistency roughly says that, in the
limit as one obtains more and more data, the learned hypothesis approaches the
best possible. Consistency depends crucially on the choice of link function
that maps surrogate reports (predictions) to target reports.

In this section, we introduce notation and concepts related to consistency
that we use throughout. Consistency is often a difficult condition to work
with directly, but in finite prediction settings, it is equivalent the simpler
notion of _calibration_ (Definition 4) which depends solely on the conditional
distribution over the labels [7, 54, 43]. Even simpler than calibration
indirect elicitation, a weaker condition only requiring that optimal surrogate
reports link to optimal target reports. Finally, we introduce a new precise
notion of embedding, a special case of indirect elicitation, which forms the
backbone of our approach.

###  2.1 Notation and Losses

Let $\mathcal{Y}$ be a finite label space, and throughout let
$n=|\mathcal{Y}|$. Define $\mathbb{R}^{\mathcal{Y}}_{+}$ to be the nonnegative
orthant in $\mathbb{R}^{\mathcal{Y}}$, i.e.,
$\mathbb{R}^{\mathcal{Y}}_{+}=\\{x\in\mathbb{R}^{\mathcal{Y}}:\forall
y\in\mathcal{Y}\;x_{y}\geq 0\\}$. Let
$\Delta_{\mathcal{Y}}=\\{p\in\mathbb{R}^{\mathcal{Y}}_{+}:\|p\|_{1}=1\\}$ be
the set of probability distributions on $\mathcal{Y}$, represented as vectors.
We will primarily focus on conditional distributions
$p\in\Delta_{\mathcal{Y}}$ over labels, abstracting away the feature space
$\mathcal{X}$; see § 2.3 for a discussion of the joint distribution over
$\mathcal{X}\times\mathcal{Y}$.

A generic loss function, denoted
$L:\mathcal{R}\to\mathbb{R}^{\mathcal{Y}}_{+}$, maps a report (prediction) $r$
from a set $\mathcal{R}$ to the vector of loss values
$L(r)=(L(r)_{y})_{y\in\mathcal{Y}}$ for each possible outcome
$y\in\mathcal{Y}$. We write the corresponding expected loss when $Y\sim p$ as
$\langle p,L(r)\rangle$. The _Bayes risk_ of a loss
$L:\mathcal{R}\to\mathbb{R}^{\mathcal{Y}}_{+}$ is the function
$\underline{L}:\Delta_{\mathcal{Y}}\to\mathbb{R}_{+}$ given by
$\underline{L}(p):=\inf_{r\in\mathcal{R}}\langle p,L(r)\rangle$. When
restricting the domain of a loss $L$ from $\mathcal{R}$ to
$\mathcal{R}^{\prime}\subseteq\mathcal{R}$, we write
$L|_{\mathcal{R}^{\prime}}$.

We assume that the target prediction problem is given in the form of a _target
loss_ $\ell:\mathcal{R}\to\mathbb{R}^{\mathcal{Y}}_{+}$ for some report set
$\mathcal{R}$. A _discrete (target) loss_ is such an $\ell$ where
$\mathcal{R}$ is a finite set. Surrogate losses will take
$\mathcal{R}=\mathbb{R}^{d}$ and be written
$L:\mathbb{R}^{d}\to\mathbb{R}^{\mathcal{Y}}_{+}$, typically with reports
written $u\in\mathbb{R}^{d}$.

For example, 0-1 loss is a discrete loss with
$\mathcal{R}=\mathcal{Y}=\\{-1,1\\}$ given by
$\ell_{\text{0-1}}(r)_{y}=\mathbbm{1}\\{r\neq y\\}$, with Bayes risk
$\underline{\ell_{\text{0-1}}}(p)=1-\max_{y\in\mathcal{Y}}p_{y}$. Two widely-
used surrogates for $\ell_{\text{0-1}}$ are hinge loss
$L_{\mathrm{hinge}}(u)_{y}=(1-yu)_{+}$, where $(x)_{+}=\max(x,0)$, and
logistic loss $L(u)_{y}=\log(1+\exp(-yu))$ for $u\in\mathbb{R}$. See Figure 1
for a visualization of the Bayes risks of 0-1, hinge, and logistic losses,
respectively.

Many of the surrogate losses we consider will be _polyhedral_ , meaning
piecewise linear and convex; we briefly recall the relevant definitions. In
$\mathbb{R}^{d}$, a _polyhedral set_ or _polyhedron_ is the intersection of a
finite number of closed halfspaces. A _polytope_ is a bounded polyhedral set.
A convex function $f:\mathbb{R}^{d}\to\mathbb{R}$ is _polyhedral_ if its
epigraph is polyhedral, or equivalently, if it can be written as a pointwise
maximum of a finite set of affine functions [50].

######  Definition 1 (Polyhedral loss).

A loss $L:\mathbb{R}^{d}\to\mathbb{R}^{\mathcal{Y}}_{+}$ is _polyhedral_ if
$L(u)_{y}$ is a polyhedral function of $u$ for each $y\in\mathcal{Y}$.

In the example above, hinge loss is polyhedral, whereas logistic loss is not.

###  2.2 Property Elicitation

We will frequently appeal to concepts and results from property elicitation
[51, 40, 32, 28, 53, 22, 31]. Here one studies _properties_ , maps from label
distributions to reports, and asks when a property characterizes the reports
that exactly minimize a loss. In our case, this map will at times be set-
valued, meaning a single distribution could yield multiple optimal reports.
For example, when $p=(1/2,1/2)$, both $r=1$ and $r=-1$ optimize 0-1 loss. We
will use double arrow notation to denote a (non-empty) set-valued map, so that
$\Gamma:\Delta_{\mathcal{Y}}\rightrightarrows\mathcal{R}$ is shorthand for
$\Gamma:\Delta_{\mathcal{Y}}\to 2^{\mathcal{R}}\setminus\\{\emptyset\\}$,
where $2^{\mathcal{R}}$ denotes the power set of $\mathcal{R}$.

######  Definition 2 (Property, level set).

A _property_ is a function
$\Gamma:\Delta_{\mathcal{Y}}\rightrightarrows\mathcal{R}$. The _level set_ of
$\Gamma$ for report $r$ is the set
$\Gamma_{r}:=\\{p\in\Delta_{\mathcal{Y}}\mid r\in\Gamma(p)\\}$. If
$\mathcal{R}$ is finite, we call $\Gamma$ a _finite property_.

Intuitively, $\Gamma(p)$ is the set of reports which should optimize expected
loss for a given distribution $p$, and $\Gamma_{r}$ is the set of
distributions for which the report $r$ should be optimal. For example, the
_mode_ is the property
$\mathrm{mode}(p)=\operatorname*{arg\,max}_{y\in\mathcal{Y}}p_{y}$, and
captures the set of optimal reports for 0-1 loss: for each distribution over
the labels, one should report the most likely label. In this case we say 0-1
loss (directly) _elicits_ the mode, as we formalize below.

######  Definition 3 (Directly Elicits).

A loss $L:\mathcal{R}\to\mathbb{R}^{\mathcal{Y}}_{+}$, _(directly) elicits_ a
property $\Gamma:\Delta_{\mathcal{Y}}\rightrightarrows\mathcal{R}$ if

$\forall
p\in\Delta_{\mathcal{Y}},\;\;\;\Gamma(p)=\operatorname*{arg\,min}_{r\in\mathcal{R}}\langle
p,L(r)\rangle~{}.$ (1)

If $L$ elicits a property, that property is unique and we denote it
$\mathrm{prop}[L]$.

Since we have defined a property $\Gamma$ to be nonempty, if the infimum of
expected loss $\langle p,L(\cdot)\rangle$ is not attained for some
$p\in\Delta_{\mathcal{Y}}$, then $L$ does not elicit a property. We say that a
loss $L$ is _minimizable_ if the infimum of $\langle p,L(\cdot)\rangle$ is
attained for all $p\in\Delta_{\mathcal{Y}}$. For example, hinge loss is
minimizable, whereas logistic loss is not (take $p=(0,1)$ or $(1,0)$).

We will typically denote general properties and losses with $\Gamma$ and $L$,
respectively. For surrogate losses and properties, recall that we typically
consider the report set $\mathbb{R}^{d}$. For discrete target losses and
properties, we will take $\mathcal{R}$ to be a finite set, and use lowercase
notation $\gamma$ and $\ell$, respectively.

###  2.3 Calibration and Links

To assess whether a surrogate and link function align with the original loss,
we turn to the common condition of _calibration_. Roughly, a surrogate and
link are calibrated if the best possible expected loss achieved by linking to
an incorrect report is strictly suboptimal.

######  Definition 4.

Let discrete loss $\ell:\mathcal{R}\to\mathbb{R}^{\mathcal{Y}}_{+}$, proposed
surrogate $L:\mathbb{R}^{d}\to\mathbb{R}^{\mathcal{Y}}_{+}$, and link function
$\psi:\mathbb{R}^{d}\to\mathcal{R}$ be given. We say $(L,\psi)$ is
_calibrated_ with respect to $\ell$ if for all $p\in\Delta_{\mathcal{Y}}$,

$\inf_{u\in\mathbb{R}^{d}:\psi(u)\not\in\mathrm{prop}[\ell](p)}\langle
p,L(u)\rangle>\inf_{u\in\mathbb{R}^{d}}\langle p,L(u)\rangle~{}.$ (2)

If $(L,\psi)$ is calibrated with respect to $\ell$, we call $\psi$ a
_calibrated link._

It is well-known in finite-outcome settings that calibration is equivalent to
_consistency_ , in the following sense (cf. [7, 63, 2]). Suppose we have the
feature space $\mathcal{X}$ and label space $\mathcal{Y}$. We say a surrogate
and link pair $(L,\psi)$ is consistent with respect to $\ell$ if, for all data
distributions $D\in\Delta(\mathcal{X}\times\mathcal{Y})$, and all sequences of
surrogate hypotheses $H_{1},H_{2},\ldots$ whose $L$-loss limits to the optimal
surrogate loss $L^{*}$ (in expectation over $D$), the $\ell$-loss of the
sequence $\psi\circ H_{1},\psi\circ H_{2},\ldots$ limits to the optimal target
loss $\ell^{*}$. As Definition 4 does not involve the feature space
$\mathcal{X}$, we will drop it for the remainder of the paper.

Like the use of a surrogate and link pair in the calibration definition, one
can also extend the earlier definition of property elicitation to _indirect
(property) elicitation_ , in which one applies a link to an elicited property
to obtain a related property of interest.

######  Definition 5.

Let minimizable loss $L:\mathbb{R}^{d}\to\mathbb{R}^{\mathcal{Y}}_{+}$ and
link $\psi:\mathbb{R}^{d}\to\mathcal{R}$ be given. The pair $(L,\psi)$
indirectly elicits a property
$\gamma:\Delta_{\mathcal{Y}}\rightrightarrows\mathcal{R}$ if for all
$u\in\mathbb{R}^{d}$, we have $\Gamma_{u}\subseteq\gamma_{\psi(u)}$, where
$\Gamma=\mathrm{prop}[L]$. Moreover, we say $L$ indirectly elicits $\gamma$ if
such a $\psi$ exists, i.e., if for all $u\in\mathbb{R}^{d}$ there exists
$r\in\mathcal{R}$ such that $\Gamma_{u}\subseteq\gamma_{r}$. 111The
elicitation literature often refers to this latter condition as one property
“refining” another [23].

Indirect elicitation is a weaker condition than calibration [52, 2, 18]; we
briefly sketch the argument. Suppose $L$ is minimizable and $(L,\psi)$ is
calibrated with respect to $\ell$, and set $\Gamma=\mathrm{prop}[L]$ and
$\gamma=\mathrm{prop}[\ell]$. Let $u\in\mathbb{R}^{d}$ and $p\in\Gamma_{u}$.
From eq. (2), if $\psi(u)\notin\gamma(p)$, then we would have
$u\notin\Gamma(p)$, a contradiction to $p\in\Gamma_{u}$. Thus,
$\psi(u)\in\gamma(p)$, so $p\in\gamma_{\psi(u)}$. In fact, indirect
elicitation is strictly weaker; take hinge loss with the link $\psi(u)=-1$ for
$u<1$ and $\psi(u)=1$ for $u\geq 1$. Agarwal and Agarwal [2] were the first to
formally connect property elicitation to calibration, though their results
generally do not apply to discrete prediction tasks.

###  2.4 Embedding

We now formalize the sense in which a convex surrogate can _embed_ a target
loss $\ell$. Here one maps each report (prediction) of $\ell$ to a point in
$\mathbb{R}^{d}$, then constructs a convex loss on $\mathbb{R}^{d}$ that
agrees with $\ell$ at these points. This approach captures several consistent
surrogates in the literature (e.g., [42, 43, 33, 55]; see § 5).

An important subtlety is that it is not always necessary to map _all_ target
reports to $\mathbb{R}^{d}$. It is often convenient to allow $\ell$ to have
reports that are “redundant” in some sense. (We explore redundancy further in
§ 6; see also Wang and Scott [55].) Because of this redundancy, we will only
require an embedding map to be defined on a _representative set_ : a set of
reports $\mathcal{S}$ such that, for all label distributions, at least one
report $r\in\mathcal{S}$ minimizes expected loss.

######  Definition 6 (Representative set).

Let $\Gamma:\Delta_{\mathcal{Y}}\rightrightarrows\mathcal{R}$. We say
$\mathcal{S}\subseteq\mathcal{R}$ is _representative for $\Gamma$_ if we have
$\Gamma(p)\cap\mathcal{S}\neq\emptyset$ for all $p\in\Delta_{\mathcal{Y}}$. We
further say $\mathcal{S}$ is a _minimum representative set_ if it has the
smallest cardinality among all representative sets. Given a minimizable loss
$L:\mathcal{R}\to\mathbb{R}^{\mathcal{Y}}_{+}$, we say $\mathcal{S}$ is a
(minimum) representative set for $L$ if it is a (minimum) representative set
for $\mathrm{prop}[L]$.

Wang and Scott [55] first study the notion of minimum representative sets
under the name _embedding cardinality_.

We now define an embedding, which is a special case of indirect property
elicitation. (This fact is non-trivial; see Lemma 11.) In addition to matching
loss values, as described above, we require the original reports to be
$\ell$-optimal exactly when the corresponding embedded points are $L$-optimal.
As we discuss following Proposition 1, this latter condition can be more
simply stated: the representative set for the target must embed into a
representative set for the surrogate.

######  Definition 7 (Embedding).

A minimizable loss $L:\mathbb{R}^{d}\to\mathbb{R}^{\mathcal{Y}}_{+}$ _embeds_
a loss $\ell:\mathcal{R}\to\mathbb{R}^{\mathcal{Y}}_{+}$ if there exists a
representative set $\mathcal{S}$ for $\ell$ and an injective embedding
$\varphi:\mathcal{S}\to\mathbb{R}^{d}$ such that (i) for all $r\in\mathcal{S}$
we have $L(\varphi(r))=\ell(r)$, and (ii) for all
$p\in\Delta_{\mathcal{Y}},r\in\mathcal{S}$ we have

$r\in\mathrm{prop}[\ell](p)\iff\varphi(r)\in\mathrm{prop}[L](p)~{}.$ (3)

If $\mathcal{S}$ is a minimal representative set, we say $L$ _tightly embeds_
$\ell$.

To illustrate the idea of embedding, let us closely examine hinge loss as a
surrogate for 0-1 loss in binary classification. Recall that we have
$\mathcal{R}=\mathcal{Y}=\\{-1,+1\\}$, with
$L_{\mathrm{hinge}}(u)_{y}=(1-uy)_{+}$ and
$\ell_{\text{0-1}}(r)_{y}:=\mathbbm{1}\\{r\neq y\\}$, typically with link
function $\psi(u)=\operatorname*{sgn}(u)$. We will see that hinge loss embeds
(2 times) 0-1 loss, via the identity embedding $\varphi(r)=r$. For condition
(i), it is straightforward to check that
$L_{\mathrm{hinge}}(\varphi(r))_{y}=L_{\mathrm{hinge}}(r)_{y}=2\mathbbm{1}\\{r\neq
y\\}=2\ell_{\text{0-1}}(r)_{y}$ for all $r,y\in\\{-1,1\\}$. For condition
(ii), let us compute the property each loss elicits, i.e., the set of optimal
reports for each $p\in\Delta_{\mathcal{Y}}$:

$\mathrm{prop}[\ell_{\text{0-1}}](p)=\begin{cases}1&p_{1}>1/2\\\
\\{-1,1\\}&p_{1}=1/2\\\
-1&p_{1}<1/2\end{cases}\qquad\mathrm{prop}[L_{hinge}](p)=\begin{cases}[1,\infty)&p_{1}=1\\\
1&p_{1}\in(1/2,1)\\\ [-1,1]&p_{1}=1/2\\\ -1&p_{1}\in(0,1/2)\\\
(-\infty,-1]&p_{1}=0\end{cases}~{}.$

In particular, we see that $-1\in\mathrm{prop}[\ell_{\text{0-1}}](p)\iff
p_{1}\in[0,1/2]\iff-1\in\mathrm{prop}[L_{\mathrm{hinge}}](p)$, and
$1\in\mathrm{prop}[\ell_{\text{0-1}}](p)\iff p_{1}\in[1/2,1]\iff
1\in\mathrm{prop}[L_{\mathrm{hinge}}](p)$. With both conditions of Definition
7 satisfied, we can conclude that $L_{\mathrm{hinge}}$ embeds
$2\ell_{\text{0-1}}$ with the representative set $\mathcal{S}=\\{-1,1\\}$. By
results in § 6.2, one could also show that $L_{\mathrm{hinge}}$ embeds
$2\ell_{\text{0-1}}$ by the fact that their Bayes risks match (Figure 1).

Figure 1: Bayes risks $\underline{L}:p\mapsto\inf_{u}\langle p,L(u)\rangle$ of
0-1, hinge, and logistic losses, respectively, plotted as a function of
$p_{1}=\Pr[Y=1]$. Observe that the Bayes risks of 0-1 and hinge loss are both
piecewise linear and concave, while the Bayes risk of logistic loss is not
piecewise linear. Proposition 2 states that embedding is equivalent to
matching Bayes risks, confirming that hinge loss (M) embeds 0-1 loss (L), but
logistic loss (R) does not.

In this particular example, it is known
$(L_{\mathrm{hinge}},\operatorname*{sgn})$ is calibrated with respect to 0-1
loss. Beyond this simple case, however, it is not clear whether an embedding
will always yield a calibrated link. Indeed, while it is intuitively clear
that embedded points should link back to their original reports, via
$\psi(\varphi(r))=r$, how to map the remaining values is far from obvious.
Using the strong connection between embeddings and polyhedral surrogates in §
3, we give a construction to map the remaining values in § 4, showing that
embeddings from polyhedral surrogates always yield calibration.

While our notion of embedding is sufficient for calibration (and therefore
consistency), it is worth noting that an embedding is not _necessary_ for
these conditions. For example, while logistic loss does not embed 0-1 loss,
logistic loss and the sign link are still consistent for 0-1 loss. When
working with polyhedral surrogates, however, embeddings are necessary for
calibration in a strong sense, as we discuss in § 7: if a polyhedral surrogate
$L$ has a calibrated link to some target $\ell$, then $L$ must embed some
discrete target $\hat{\ell}$ which can then be linked to $\ell$.

##  3 Embeddings and Polyhedral Losses

In this section, we establish a tight relationship between the technique of
embedding and the use of polyhedral (piecewise-linear convex) surrogate
losses, culminating in Theorem 1. We defer the question of when such
surrogates are consistent to § 4.

A first observation is that if a loss $L$ elicits a property $\Gamma$, then
$L$ restricted to some representative set $\mathcal{S}$, denoted
$L|_{\mathcal{S}}$, elicits $\Gamma$ restricted to $\mathcal{S}$. As a
consequence, restricting to representative sets preserves the Bayes risk. We
will use these observations throughout.

######  Lemma 1.

Let $L:\mathcal{R}\to\mathbb{R}^{\mathcal{Y}}_{+}$ elicit $\Gamma$, and let
$\mathcal{S}\subseteq\mathcal{R}$ be representative for $L$. Then
$L|_{\mathcal{S}}$ elicits
$\gamma:\Delta_{\mathcal{Y}}\rightrightarrows\mathcal{S}$ defined by
$\gamma(p)=\Gamma(p)\cap\mathcal{S}$. Moreover,
$\underline{L}=\underline{L|_{\mathcal{S}}}$.

###### Proof.

Let $p\in\Delta_{\mathcal{Y}}$ be fixed throughout. First let
$r\in\gamma(p)=\Gamma(p)\cap\mathcal{S}$. Then
$r\in\Gamma(p)=\operatorname*{arg\,min}_{u\in\mathcal{R}}\langle
p,L(u)\rangle$, so as $r\in\mathcal{S}$ we have in particular
$r\in\operatorname*{arg\,min}_{u\in\mathcal{S}}\langle p,L(u)\rangle$. For the
other direction, suppose
$r\in\operatorname*{arg\,min}_{u\in\mathcal{S}}\langle p,L(u)\rangle$. As
$\mathcal{S}$ is representative for $L$, we must have some
$s\in\Gamma(p)\cap\mathcal{S}$. On the one hand,
$s\in\Gamma(p)=\operatorname*{arg\,min}_{u\in\mathcal{R}}\langle
p,L(u)\rangle$. On the other, as $s\in\mathcal{S}$, we certainly have
$s\in\operatorname*{arg\,min}_{u\in\mathcal{S}}\langle p,L(u)\rangle$. But now
we must have $\langle p,L(r)\rangle=\langle p,L(s)\rangle$, and thus
$r\in\operatorname*{arg\,min}_{u\in\mathcal{R}}\langle
p,L(u)\rangle=\Gamma(p)$ as well. We now see $r\in\Gamma(p)\cap\mathcal{S}$.
Finally, the equality of the Bayes risks $\min_{u\in\mathcal{R}}\langle
p,L(u)\rangle=\min_{u\in\mathcal{S}}\langle p,L(u)\rangle$ follows immediately
by the above, as $\emptyset\neq\Gamma(p)\cap\mathcal{S}\subseteq\Gamma(p)$ for
all $p\in\Delta_{\mathcal{Y}}$. ∎

Lemma 1 leads to the following useful tool for finding embeddings: if a
surrogate has a finite representative set, it embeds its restriction to the
representative set.

######  Proposition 1.

Let a minimizable surrogate loss
$L:\mathbb{R}^{d}\to\mathbb{R}^{\mathcal{Y}}_{+}$ be given. If $L$ has a
finite representative set $\mathcal{S}\subseteq\mathbb{R}^{d}$, then $L$
embeds the discrete loss $L|_{\mathcal{S}}$.

###### Proof.

Let $\Gamma=\mathrm{prop}[L]$ and $\gamma=\mathrm{prop}[L|_{\mathcal{S}}]$.
Define $\varphi:\mathcal{S}\to\mathcal{S}$ to be the identity embedding.
Condition (i) of an embedding is trivially satisfied, as
$L|_{\mathcal{S}}(u)=L(u)$ for all $u\in\mathcal{S}$. Now let
$u\in\mathcal{S}$. From Lemma 1, for all $p\in\Delta_{\mathcal{Y}}$ we have
$u\in\gamma(p)\iff u\in\Gamma(p)\cap\mathcal{S}\iff u\in\Gamma(p)$. We
conclude condition (ii) of an embedding. ∎

Proposition 1 reveals an equivalent definition of an embedding which can be
more convenient. Given a representative set $\mathcal{S}$ for $\ell$, an
injection $\varphi:\mathcal{S}\to\mathbb{R}^{d}$ is an embedding if: (i) the
loss values match as in Definition 7(i), and (ii) $\varphi(\mathcal{S})$ is
representative for $L$. This new definition is clearly implied by Definition
7; for the converse, Proposition 1 states that $L$ embeds
$L|_{\varphi(\mathcal{S})}$, which by (i) is the same loss as $\ell$ up to
relabeling via $\varphi$.

With Proposition 1 in hand, we now shift our focus to _polyhedral_ (piecewise-
linear and convex) surrogates. While polyhedral surrogates do not directly
elicit finite properties, as their report sets are infinite, they do elicit
properties with a finite range, meaning the set of possible optimal report
sets is finite.

######  Lemma 2.

Let $L:\mathbb{R}^{d}\to\mathbb{R}_{+}^{\mathcal{Y}}$ be a polyhedral loss.
Then $L$ is minimizable and elicits a property $\Gamma:=\mathrm{prop}[L]$.
Moreover, the range of $\Gamma$, given by
$\Gamma(\Delta_{\mathcal{Y}})=\\{\Gamma(p)\subseteq\mathbb{R}^{d}:p\in\Delta_{\mathcal{Y}}\\}$,
is a finite set of closed polyhedra.

###### Proof sketch.

See § A for the full proof. As $L$ is bounded from below, $L$ is minimizable
from Rockafellar [50, Corollary 19.3.1] . With $\mathcal{Y}$ finite, there are
only finitely many supporting sets over $\Delta_{\mathcal{Y}}$. For
$p\in\Delta_{\mathcal{Y}}$, the power diagram induced by projecting the
epigraph of expected loss onto $\mathbb{R}^{d}$ is the same for any $p$ of the
same support (Lemma 5). Moreover, we have $\Gamma(p)$ being exactly one of the
faces of the projected epigraph since the hyperplane $u\mapsto(u,\langle
p,L(u)\rangle)$ supports the epigraph of the expected loss at exactly the
property value; moreover, since the loss is polyhedral the supporting
hyperplane must support on a face of the epigraph. Since this epigraph has
finitely many faces (as it is polyhedral), the range of $\Gamma$ is then (a
subset) of elements of a finitely generated (finite supports) set of finite
elements (finite faces). Moreover, each element of
$\Gamma(\Delta_{\mathcal{Y}})$ is a closed polyhedron since it corresponds
exactly to a closed face of a polyhedral set. ∎

From Lemma 2, one can simply select a point from each of the finitely many
optimal sets to obtain a finite representative set. Plugging this finite
representative set into Proposition 1 then yields an embedding.

######  Theorem 3.

Every polyhedral loss $L$ embeds a discrete loss.

###### Proof.

Let $L:\mathbb{R}^{d}\to\mathbb{R}_{+}^{\mathcal{Y}}$ be a polyhedral loss,
and $\Gamma=\mathrm{prop}[L]$. By Lemma 2, $\Gamma(\Delta_{\mathcal{Y}})$ is
finite set. For each $U\in\Gamma(\Delta_{\mathcal{Y}})$, select $u_{U}\in U$,
and let $\mathcal{S}=\\{u_{U}:U\in\Gamma(\Delta_{\mathcal{Y}})\\}$, which is
again finite. For any $p\in\Delta_{\mathcal{Y}}$ then, let $U=\Gamma(p)$. We
have $U\in\Gamma(\Delta_{\mathcal{Y}})$ by definition, and thus some
$u_{U}\in\mathcal{S}$; in particular, $u_{U}\in U=\Gamma(p)$. We conclude that
$\mathcal{S}$ is representative for $L$. Proposition 1 now states that $L$
embeds $L|_{\mathcal{S}}$. ∎

We now turn to the reverse direction: which discrete losses are embedded by
some polyhedral loss? Perhaps surprisingly, we show in Theorem 4 that _every_
discrete loss is embeddable by a polyhedral surrogate. Combining this result
with Theorem 3 establishes Theorem 1. Further combining with Theorem 2, proved
in the following section, this construction gives a calibrated polyhedral
surrogate for every discrete target loss.

In the proof, we apply a result we will prove in § 6: a minimizable surrogate
embeds a discrete loss if and only if their Bayes risks match (Proposition 2).

######  Theorem 4.

Every discrete loss $\ell:\mathcal{R}\to\mathbb{R}^{\mathcal{Y}}_{+}$ is
embedded by a polyhedral loss.

###### Proof.

Let $n=|\mathcal{Y}|$, and let $C:\mathbb{R}^{n}\to\mathbb{R}$ be given by
$(-\underline{\ell})^{*}$, the convex conjugate of $-\underline{\ell}$. From
standard results in convex analysis, $C$ is polyhedral as $-\underline{\ell}$
is, and $C$ is finite on all of $\mathbb{R}^{\mathcal{Y}}$ as the domain of
$-\underline{\ell}$ is bounded [50, Corollary 13.3.1]. Note that
$-\underline{\ell}$ is a closed convex function, as the infimum of affine
functions, and thus $(-\underline{\ell})^{**}=-\underline{\ell}$. Define
$L:\mathbb{R}^{n}\to\mathbb{R}^{\mathcal{Y}}$ by $L(u)=C(u)\mathbbm{1}-u$,
where $\mathbbm{1}\in\mathbb{R}^{\mathcal{Y}}$ is the all-ones vector. As $C$
is polyhedral, so is $L$. We first show that $L$ embeds $\ell$, and then
establish that the range of $L$ is in fact $\mathbb{R}^{\mathcal{Y}}_{+}$, as
desired.

We compute Bayes risks and apply Proposition 2 to see that $L$ embeds $\ell$.
Observe that $\underline{\ell}$ is polyhedral as $\ell$ is discrete. For any
$p\in\Delta_{\mathcal{Y}}$, we have

$\displaystyle\underline{L}(p)$
$\displaystyle=\inf_{u\in\mathbb{R}^{n}}\langle p,C(u)\mathbbm{1}-u\rangle$
$\displaystyle=\inf_{u\in\mathbb{R}^{n}}C(u)-\langle p,u\rangle$
$\displaystyle=-\sup_{u\in\mathbb{R}^{n}}\langle p,u\rangle-C(u)$
$\displaystyle=-C^{*}(p)=-(-\underline{\ell}(p))^{**}=\underline{\ell}(p)~{}.$

It remains to show $L(u)_{y}\geq 0$ for all $u\in\mathbb{R}^{n}$,
$y\in\mathcal{Y}$. Letting $\delta_{y}\in\Delta_{\mathcal{Y}}$ be the point
distribution on outcome $y\in\mathcal{Y}$, we have for all
$u\in\mathbb{R}^{n}$,
$L(u)_{y}\geq\inf_{u^{\prime}\in\mathbb{R}^{n}}L(u^{\prime})_{y}=\underline{L}(\delta_{y})=\underline{\ell}(\delta_{y})\geq
0$, where the final inequality follows from the nonnegativity of $\ell$. ∎

The proof of Theorem 4 uses a construction via convex conjugate duality
similar to many constructions in the literature. For example, the min-max
objective in the literature on adversarial prediction [3, 14, 15, 16] is a
special case of this construction when one unfolds the definition of the
convex conjugate of $-\underline{\ell}$. Reid et al. [47] construct a
canonical link function for proper losses with differentiable Bayes risks; the
link maps a report $p\in\Delta_{\mathcal{Y}}$ to the gradient of the Bayes
risk at $p$, which uses the same duality as above. Duchi et al. [12,
Proposition 3] give essentially the same construction as ours, but only
comment on the calibration of surrogates under such constructions for
multiclass classification tasks given by strictly concave losses, excluding
polyhedral surrogates. Finally, a similar construction also appears in the
design of prediction markets [1] and in connections between proper losses and
mechanism design [21].

##  4 Consistency and Linear Regret Transfer via Separated Links

We have seen that every polyhedral loss embeds some discrete loss. The
embedding itself tells us how to link the embedded points back to the discrete
reports: link $\varphi(r)$ back to $r$. But it is not clear how to extend this
to yield a full link function $\psi:\mathbb{R}^{d}\to\mathcal{R}$, and whether
such a $\psi$ can lead to consistency. In this section, we prove Theorem 2,
restated below, via a construction to generate calibrated links for _any_
polyhedral surrogate. Recalling that calibration is equivalent to consistency
for discrete targets, this result implies that an embedding always yields
consistency.

The key idea behind our construction is the notion of _separation_ , a
condition which is equivalent to calibration for discrete prediction problems.
Roughly, given a surrogate $L$ and discrete target $\ell$, a link is
$\epsilon$-separated if the distance between any $L$-optimal point in
$\mathbb{R}^{d}$, and any point that links to an $\ell$-suboptimal report, is
at least $\epsilon$. We also show how this characterization also leads to
linear _regret transfer_ or _surrogate regret_ bounds.

###  4.1 Separation

Recall that for indirect elicitation, any point $u\in\Gamma(p)$ must link to a
report $\psi(u)\in\gamma(p)$. (In terms of losses, $u$ minimizing expected
$L$-loss implies that $\psi(u)$ minimizes expected $\ell$-loss, with respect
to $p$.) The idea of separation is that points in the neighborhood of $u$ must
also link to to a report in $\gamma(p)$. Furthermore, there must be a uniform
lower bound $\epsilon$ on the size of any such neighborhood.

######  Definition 8 (Separated Link).

Let properties $\Gamma:\Delta_{\mathcal{Y}}\rightrightarrows\mathbb{R}^{d}$
and $\gamma:\Delta_{\mathcal{Y}}\rightrightarrows\mathcal{R}$ be given. We say
a link $\psi:\mathbb{R}^{d}\to\mathcal{R}$ is _$\epsilon$ -separated with
respect to $\Gamma$ and $\gamma$_ if for all $u\in\mathbb{R}^{d}$,
$p\in\Delta_{\mathcal{Y}}$ with $\psi(u)\notin\gamma(p)$, we have
$d_{\infty}(u,\Gamma(p))\geq\epsilon$, where $d_{\infty}(u,A)\doteq\inf_{a\in
A}\|u-a\|_{\infty}$. 222Frongillo and Waggoner [24] define
$\epsilon$-separation with a strict inequality
$d_{\infty}(u,\Gamma(p))>\epsilon$; we adopt a weak inequality as it is more
natural in applications, such as hinge loss for binary classification.
Similarly, we say $\psi$ is $\epsilon$-separated with respect to $L$ and
$\ell$ if it is $\epsilon$-separated with respect to $\mathrm{prop}[L]$ and
$\mathrm{prop}[\ell]$.

######  Theorem 5.

Let polyhedral surrogate $L:\mathbb{R}^{d}\to\mathbb{R}^{\mathcal{Y}}_{+}$,
discrete loss $\ell:\mathcal{R}\to\mathbb{R}^{\mathcal{Y}}_{+}$, and link
$\psi:\mathbb{R}^{d}\to\mathcal{R}$ be given. Then $(L,\psi)$ is calibrated
with respect to $\ell$ if and only if $\psi$ is $\epsilon$-separated with
respect to $L$ and $\ell$ for some $\epsilon>0$.

Intuitively, calibration of a polyhedral surrogate and separated link follows
from two facts. First, Lemma 2 states that a polyhedral surrogate has only a
finite number of “optimal report sets”
$\\{\Gamma(p):p\in\Delta_{\mathcal{Y}}\\}$. Second, for a given $p$, the
expected surrogate loss for a suboptimal point scales with the distance from
the optimal set $\Gamma(p)$ at some minimum linear rate $\alpha>0$; this rate
is related to _Hoffman constants_. Combining with the first fact gives a
universal minimum constant $\alpha$ for all $p$. Now bringing in
$\epsilon$-separation, any surrogate report linking to a suboptimal target
report has expected surrogate loss at least $\alpha\cdot\epsilon>0$. On the
other hand, if a link is not separated, then the same two facts imply that,
for a sequence of surrogate reports that get arbitrarily close to an optimal
report set while linking to a suboptimal target report, this sequence has
expected loss approaching optimal, violating calibration. See § B for the
proof.

###  4.2 Consistency

To prove Theorem 2, that embedding implies calibration, we now show how to
construct a calibrated link from an embedding. In light of Theorem 5, it now
suffices to show that for any polyhedral $L$ embedding some $\ell$, there
exists a _separated_ link $\psi$ with respect to $L$ and $\ell$. Construction
1, discussed next, “thickens” a given embedding to produce a link. Theorem 6
states that, for a small enough choice of $\epsilon$, that link is separated.
See § D for the proof.

######  Theorem 6.

Let polyhedral surrogate $L:\mathbb{R}^{d}\to\mathbb{R}^{\mathcal{Y}}_{+}$
embed the discrete loss $\ell:\mathcal{R}\to\mathbb{R}^{\mathcal{Y}}_{+}$.
Then there exists $\epsilon_{0}>0$ such that, for all
$0<\epsilon\leq\epsilon_{0}$, Construction 1 for $L,\ell,\epsilon,\|\cdot\|$
produces a nonempty set of links, all of which are $\epsilon$-separated with
respect to $L$ and $\ell$.

To set the stage for Construction 1, we sketch the two main steps in proving
Theorem 6: (i) showing that one can define a link $\psi$ on all possible
optimal points of $L$; (ii) “thickening” $\psi$ so that it is separated.

For (i), given the embedding $\varphi:\mathcal{S}\to\mathbb{R}^{d}$, begin by
linking each embedding point back to its original report, so that
$\psi(\varphi(r))=r$. Now we wish to determine $\psi(u)$ for non-embedding
points $u\in\mathbb{R}^{d}$ which optimize $L$ for some distribution. Let
$\Gamma=\mathrm{prop}[L]$ and define $\mathcal{U}=\\{\Gamma(p)\mid
p\in\Delta_{\mathcal{Y}}\\}$ to be the “range” of $\Gamma$, i.e., all possible
optimal sets. For each $U\in\mathcal{U}$, we can define
$R_{U}=\\{r\in\mathcal{S}\mid\varphi(r)\in U\\}$ to be the set of target
reports which, by definition of embedding, are $\ell$-optimal when $U$ is
$L$-optimal. We would like to restrict $\psi(U)\subseteq R_{U}$, so that
optimal surrogate reports are mapped to optimal target reports. The challenge
is that we could have a point $u\in U\cap U^{\prime}$ for two optimal sets
$U,U^{\prime}\in\mathcal{U}$, and _a priori_ , it could be that $R_{U}\cap
R_{U^{\prime}}=\emptyset$. The first step of the proof is to show that this
scenario cannot arise.

$\forall\mathcal{U}^{\prime}\subseteq\mathcal{U},\;\cap_{U\in\mathcal{U}^{\prime}}U\neq\emptyset\implies\cap_{U\in\mathcal{U}^{\prime}}R_{U}\neq\emptyset~{}.$
(4)

Thus, for any $u\in\cup\mathcal{U}$, we have a nonempty set of valid choices
for $\psi(u)$. (Eq. (4) may appear similar to indirect elicitation; in fact
the two conditions are equivalent, as we discuss in § 7.)

For (ii), we show that this link can be “thickened” by some positive
$\epsilon$, as described next. Let $U\in\mathcal{U}$. By the above, $\psi$ is
already correct on $U$. Now, we “thicken” $U$ to obtain
$U_{\epsilon}=\\{u:\|u-U\|\leq\epsilon\\}$. Then we require that all points in
$U_{\epsilon}$ are linked to some element of $R_{U}$. For $\epsilon>0$, this
condition directly implies separation.

It is not clear that this linking is possible, however, because a point $u$
may be in the intersection of several thickened sets
$U_{\epsilon},U^{\prime}_{\epsilon}$, etc., corresponding to
$\Gamma(p),\Gamma(p^{\prime})$, etc. Therefore, we need to take each possible
collection $U,U^{\prime}$, etc., show that their intersection (if nonempty)
contains a legal choice for the link, and then thicken their intersection in
an analogous way.

To do so, given $u\in U_{\epsilon}\cap U^{\prime}_{\epsilon}\cap\dots$, we
define a _link envelope_ $\Psi(u)$ which encodes the remaining legal choices
for $\psi(u)$ after imposing the requirements for each such set
$U_{\epsilon},U^{\prime}_{\epsilon}$, etc. The key claim is that, for small
enough $\epsilon>0$, $\Psi(u)$ is nonempty: at least one permitted value for
$\psi(u)$ remains. This claim follows from a geometric result (Lemma 13) that,
for all small enough $\epsilon$, a subset of thickenings $U_{\epsilon}$
intersect if and only if the $U$ sets themselves intersect. When they do
intersect, eq. (4) implies that there exists a permitted choice of link for
the intersection of the thickenings. It is crucial that, by Lemma 2,
polyhedral surrogates only have finitely many sets of the form $U=\Gamma(p)$.
Together, these observations yield a single uniform smallest $\epsilon$ such
that the key claim is true for all $u\in\mathbb{R}^{d}$.

Given the above proof sketch, the following construction is relatively
straightforward. We initialize the link using the embedding points and optimal
report sets, then adjust $\Psi$ to narrow down to only legal choices; we then
pick from $\psi(u)$ from $\Psi(u)$ arbitrarily. Theorem 6 implies that, for
all small enough $\epsilon$, the resulting link $\psi$ is well-defined at all
points, and $\epsilon$-separated.

######  Construction 1 ($\epsilon$-thickened link).

Let $L:\mathbb{R}^{d}\to\mathbb{R}^{\mathcal{Y}}_{+}$,
$\ell:\mathcal{R}\to\mathbb{R}^{\mathcal{Y}}_{+}$, $\epsilon>0$, and a norm
$\|\cdot\|$ be given, such that $L$ is polyhedral and embeds $\ell$ via the
embedding $\varphi:\mathcal{S}\to\mathbb{R}^{d}$ for a representative set
$\mathcal{S}\subseteq\mathcal{R}$. Define $\Gamma=\mathrm{prop}[L]$ and
$\mathcal{U}=\\{\Gamma(p)\mid p\in\Delta_{\mathcal{Y}}\\}$. For all
$U\in\mathcal{U}$, define $R_{U}=\\{r\in\mathcal{S}\mid\varphi(r)\in U\\}$.
The _$\epsilon$ -thickened link_ $\psi$ is constructed as follows. First,
initialize the _link envelope_ $\Psi:\mathbb{R}^{d}\to 2^{\mathcal{S}}$ by
setting $\Psi(u)=\mathcal{S}$ for all $u$. Then for each $U\in\mathcal{U}$,
for all points $u$ such that $\inf_{u^{*}\in U}\|u^{*}-u\|<\epsilon$, update
$\Psi(u)=\Psi(u)\cap R_{U}$. If we have $\Psi(u)\neq\emptyset$ for all
$u\in\mathbb{R}^{d}$, then the construction _produces a link_ $\psi\in\Psi$
pointwise, breaking ties arbitrarily.

In § 7 we generalize this construction beyond embeddings, where we only
require that $L$ indirectly elicits $\mathrm{prop}[\ell]$. There we will see
that, perhaps surprisingly, this construction recovers every possible
calibrated link.

Applying Construction 1 also enables one to verify the consistency of a given
proposed link $\psi^{*}$. For a given $\epsilon$ and norm $\|\cdot\|$, suppose
one follows the routine of Construction 1 until the last step in which values
for the link $\psi$ are selected. Instead, we can simply test whether the
proposed link values are contained in the valid choices, i.e., if
$\psi^{*}(u)\in\Psi(u)$ for all $u\in\mathbb{R}^{d}$. If so, then the proposed
link $\psi^{*}$ is calibrated. See § 5.5 for an illustration of this test. On
the other hand, if $\psi^{*}$ cannot be produced from Construction 1, then it
cannot be a calibrated link. This impossibility can be shown, for example, if
there exists a point $u$ where $\Psi(u)$ is empty for all $\epsilon>0$.

Construction 1 is not necessarily computationally efficient as the number of
labels $n$ grows. In practice this potential inefficiency is not typically a
concern, as the family of losses typically has some closed form expression in
terms of $n$, and thus the construction can proceed at the symbolic level. We
illustrate this formulaic approach in § 5.2.

###  4.3 Surrogate regret bounds

Recall that the approach of surrogate risk minimization is to learn a
hypothesis $h$ that minimizes expected surrogate loss, then output hypothesis
$\psi\circ h$, which hopefully minimizes expected target loss. We would like
surrogates where a bound on surrogate loss of $h$ immediately implies a bound
on target loss of $\psi\circ h$. One can formalize this problem in terms of
_regret_ , as follows. Fix a data distribution $\mathcal{D}$. The _surrogate
regret_ $R_{L}$ of $h$ and the _target regret_ $R_{\ell}$ of the implied
hypothesis $\psi\circ h$, are given by

$\displaystyle R_{L}(h;\mathcal{D})$
$\displaystyle=\mathbb{E}_{(X,Y)\sim\mathcal{D}}L(h(X))_{Y}-\inf_{h^{\prime}:\mathcal{X}\to\mathbb{R}^{d}}\mathbb{E}_{(X,Y)\sim\mathcal{D}}L(h^{\prime}(X))_{Y}~{},$
$\displaystyle R_{\ell}(\psi\circ h;\mathcal{D})$
$\displaystyle=\mathbb{E}_{(X,Y)\sim\mathcal{D}}\ell(\psi(h(X)))_{Y}-\inf_{g^{\prime}:\mathcal{X}\to\mathcal{R}}\mathbb{E}_{(X,Y)\sim\mathcal{D}}\ell(g^{\prime}(X))_{Y}~{},$

where the infimum is taken over all measurable functions. The infimum
represents the risk of the Bayes optimal hypothesis, so regret can be viewed
as _excess risk_ under the assumption that the learner’s hypothesis class
contains the Bayes optimal.

Consistency means that if the surrogate regret of $h$ converges to zero, then
the target regret of $\psi\circ h$ does as well; in other words,
$R_{L}(h;\mathcal{D})\to 0$ implies $R_{\ell}(\psi\circ h;\mathcal{D})\to 0$.
Consistency is therefore a minimal requirement; in general, we are also
interested in the _rate_ at which the target regret diminishes, as a function
of the number of data points $n$. A _regret transfer bound_ , also called a
_surrogate regret bound_ , gives a guarantee on the relationship between the
rates of convergence of $R_{L}$ and $R_{\ell}$. For example, a surrogate with
a fast rate of convegence $R_{L}\to 0$ as $n\to\infty$ is not very useful if
we nevertheless have a slow rate $R_{\ell}\to 0$.

We show that, for any polyhedral surrogate, the transfer is linear: if
surrogate regret diminishes at a rate of $O(f(n))$, then the target rate is
also $O(f(n))$. In particular, fast convergence in surrogate regret implies
fast convergence in target regret.

######  Theorem 7.

Let $(L,\psi)$ be consistent for a discrete loss $\ell$, and $L$ polyhedral.
Then there exists $c>0$ such that, for all hypotheses $h$ and data
distributions $\mathcal{D}$, we have $R_{\ell}(\psi\circ h;\mathcal{D})\leq
c\cdot R_{L}(h;\mathcal{D})$.

In the proof (§ C), we further show that the constant $c$ can be decomposed in
terms of three constants, which depend on $L$, $\psi$, and $\ell$,
respectively. Specifically, we may write $c=C_{\ell}H_{L}/\epsilon_{\psi}$,
where $H_{L}$ is the Hoffman constant for $L$, $\epsilon_{\psi}$ the
separation of $\psi$, and $C_{\ell}$ the maximum loss gap of $\ell$. This
expression gives the intuition that larger link separation is generally better
for performance. In some cases, this bound can be tightened, as we discuss in
§ C.2. See Frongillo and Waggoner [24] for a quadratic lower bound on the rate
transfer for sufficiently non-polyhedral surrogates.

##  5 Application to Specific Surrogates

Our results give a framework to construct consistent polyhedral surrogates and
link functions for any discrete target loss, as well as to verify consistency
or inconsistency for specific surrogate and link pairs. Below, we illustrate
the power of this framework with specific examples from the literature. To
warm up, we study the abstain surrogate given by Ramaswamy et al. [44], which
is an embedding, and show how to rederive their link function and surrogate
regret bounds (§ 5.2). We then give three examples of subsequent works that
use our framework, in the context of structured binary classification (§ 5.3),
multiclass classification (§ 5.4), and top-$k$ classification (§ 5.5). In each
of these latter three examples, our framework illuminates the behavior of
inconsistent surrogates by revealing the discrete losses they embed, i.e., the
true targets for which they are consistent. In structured binary
classification and top-$k$ classification, our framework also gives new
consistent surrogates and link functions which appear challenging to derive
otherwise.

###  5.1 Applying the embedding framework

When using our framework to study the consistency or inconsistency of an
existing surrogate $L:\mathbb{R}^{d}\to\mathbb{R}^{\mathcal{Y}}_{+}$, often
the first step is determining the loss it embeds. To do so, we suggest the
following general approach. First, for each $y\in\mathcal{Y}$, divide
$\mathbb{R}^{d}$ into a finite number of polyhedral regions on which
$L(\cdot)_{y}$ is an affine function. Second, identify the vertices of these
polyhedral regions. 333In some cases, these regions do not have vertices, such
as the top-$k$ surrogates in § 5.5 which are invariant in the all-ones
direction; here one can restrict to a subspace, or otherwise select among
equivalent reports. Third, conclude that the union of these vertices,
$\mathcal{S}\subset\mathbb{R}^{d}$, is a finite representative set for $L$.
Now $L$ embeds $L|_{\mathcal{S}}$ from Proposition 1. From here one can
further remove redundant reports until arriving at a tight embedding if
desired, or re-label embedded reports to a more intuitive form; call this
resulting embedded loss $\hat{\ell}$.

Once the embedded discrete loss $\hat{\ell}$ is known, the behavior of the
surrogate $L$ becomes more clear. In particular, we learn what problem $L$ is
actually solving, as captured by $\hat{\ell}$. If this problem $\hat{\ell}$ is
not the desired target problem $\ell$, we can still derive restrictions on
label distributions (e.g., $\mathcal{P}\subseteq\Delta_{\mathcal{Y}}$) for
which $L$ is $\mathcal{P}$-calibrated for $\ell$. Any level set of the
embedded property $\hat{\gamma}=\mathrm{prop}[\hat{\ell}]$ which spans
multiple level sets of the target property $\gamma=\mathrm{prop}[\ell]$ will
lead to inconsistency for $\ell$ (Figure 2). To obtain consistency with
respect to a desired target, therefore, it suffices to restrict to the union
of level sets of $\hat{\gamma}$ which are each fully contained in some level
set of $\gamma$.

${p_{1}}$${p_{3}}$${p_{2}}$•$p$•$p^{\prime}$

Figure 2: Using an embedding to show inconsistency. Let $L$ be a surrogate
embedding $\ell$, and let $\ell$ be a desired target; here $L=L_{\text{\tiny
BEP}}$, $\hat{\ell}=\ell_{\text{abs}}$ (§ 5.2) and $\ell$ is 0-1 loss for
multiclass classification. Let $\Gamma=\mathrm{prop}[L]$,
$\hat{\gamma}=\mathrm{prop}[\hat{\ell}]$, and $\gamma=\mathrm{prop}[\ell]$ be
the properties elicited by these losses; here $\gamma=\mathrm{mode}$, as 0-1
loss elicits the mode. The level sets of $\hat{\gamma}$ are given in solid
black lines, and those of $\gamma$ in dashed blue lines. To exhibit non-
calibration, take distributions $p,p^{\prime}$ in the relative interior of the
blue cell $\hat{\gamma}_{\hat{r}}$ (here $\hat{r}=\bot$ for
$\ell_{\text{abs}}$) but in different cells of $\gamma$. These distributions
will satisfy $\hat{\gamma}(p)=\hat{\gamma}(p^{\prime})$, and thus
$\Gamma(p)=\Gamma(p^{\prime})$ by definition of embedding, but
$\gamma(p)\cap\gamma(p^{\prime})=\emptyset$. Taking
$u\in\Gamma(p)=\Gamma(p^{\prime})$, it is impossible to define $\psi(u)$ to
satisfy calibration, as $\psi(u)$ cannot be in $\gamma(p)$ and
$\gamma(p^{\prime})$ simultaneously. In particular, even though $u$ is
$L$-optimal for both $p$ and $p^{\prime}$, $\psi(u)$ will be $\ell$-suboptimal
for at least one, violating calibration. We may impose restrictions on the
conditional label distributions to remove the blue cell, however, and thus
satisfy calibration. For this example, the $L_{\text{\tiny BEP}}$ is
classification-calibrated if one restricts to the set of distributions where
at least one label $y\in\mathcal{Y}$ has probability $p_{y}\geq\tfrac{1}{2}$.

With an embedding in hand, Construction 1 provides a calibrated link function
from $L$ to $\hat{\ell}$. This construction is especially beneficial in cases
where the most intuitive link functions are not calibrated, and no known
calibrated link is known; see § 5.3 for a somewhat intricate example.
Surrogate regret bounds then follow from Theorem 7, as we illustrate in § 5.2.
In particular, our results imply the existence of linear regret transfer
bounds bounds for several applications where no such bounds were known (§ 5.3,
5.4, 5.5).

Finally, our link construction can even be useful in cases where the search
for consistent surrogates has been restricted to those accommodating a
particular canonical link function $\psi$. For example, one typically uses the
sign link for binary classification, and the argmax link (the $k$ largest
coordinates) for top-$k$ classification (§ 5.5). As we show in Proposition 9,
Construction 1 fully characterizes the set of possible calibrated link
functions for a polyhedral embedding via the link envelope $\Psi$, so $\psi$
is calibrated if and only if it is contained in $\Psi$ for some $\epsilon>0$.
We demonstrate this approach for top-$k$ classification in § 5.5. More
generally, however, while such canonical link functions may be intuitive for a
given problem, our results suggest that researchers should consider setting
them aside and instead let Construction 1 determine the link.

###  5.2 Consistency of abstain surrogate and link construction

Several authors consider a variant of multiclass classification, with the
addition of an _abstain_ option [6, 44, 37, 13, 10]. Ramaswamy et al. [44]
study the loss
$\ell_{\text{abs}}:\mathcal{Y}\cup\\{\bot\\}\to\mathbb{R}^{\mathcal{Y}}_{+}$
defined by $\ell_{\text{abs}}(r)_{y}=0$ if $r=y$, $1/2$ if $r=\bot$, and 1
otherwise. The report $\bot$ corresponds to “abstaining” to predict, in
exchange for a constant loss regardless of outcome $y$. Ramaswamy et al. give
the polyhedral _binary encoded predictions (BEP)_ surrogate $L_{\text{\tiny
BEP}}$, and the link $\psi^{\infty}$ which they show is calibrated for
$\ell_{\text{abs}}$. Letting $d=\lceil\log_{2}|\mathcal{Y}|\rceil$, their
surrogate $L_{\text{\tiny BEP}}:\mathbb{R}^{d}\to\mathbb{R}^{\mathcal{Y}}_{+}$
is given by

$L_{\text{\tiny
BEP}}(u)_{y}=\max_{j\in[d]}\left(1-\varphi(y)_{j}u_{j}\right)_{+}~{},$ (5)

where $\varphi:\mathcal{Y}\to\\{-1,1\\}^{d}$ is an injection. 444To translate
our notation to that of Ramaswamy et al. [44], take $B=-\varphi$. Observe that
$L_{\text{\tiny BEP}}$ is exactly hinge loss when $|\mathcal{Y}|=2$ and thus
$d=1$. The authors show that the link $\psi^{\infty}$ is calibrated, where

$\psi^{\infty}(u)=\begin{cases}\bot&\min_{i\in[d]}|u_{i}|\leq 1/2\\\
\varphi^{-1}(\operatorname*{sgn}(u))&\text{otherwise}\end{cases}~{},$ (6)

and they go on to establish linear surrogate regret bounds for
$(L_{\text{\tiny BEP}},\psi^{\infty})$.

Using our framework, one can show that $L_{\text{\tiny BEP}}$ embeds (2 times)
$\ell_{\text{abs}}$, with the embedding given by $\varphi$ above where we
define $\varphi(\bot)=0\in\mathbb{R}^{d}$. (Following the general procedure
outlined above, the regions where $L_{\text{\tiny BEP}}$ is affine all have
vertices in the set $\\{-1,1\\}^{d}\cup\\{0\\}$, meaning it is representative,
and $L_{\text{\tiny BEP}}$ restricted to that set is precisely
$2\ell_{\text{abs}}\circ\varphi^{-1}$.)

As an illustration, one can use the fact that $L_{\text{\tiny BEP}}$ embeds
$\ell_{\text{abs}}$ to verify that $L_{\text{\tiny BEP}}$ is inconsistent for
multiclass classification, i.e., with respect to 0-1 loss. In particular,
since the abstain report $\bot$ is $\ell_{\text{abs}}$-optimal whenever
$\max_{y\in\mathcal{Y}}p_{y}\leq 1/2$, by the definition of embedding, the
origin $0\in\mathbb{R}^{d}$ is $L_{\text{\tiny BEP}}$-optimal for the same
distributions. Recalling that 0-1 loss elicits the mode, one can now find two
distributions with different modes but for which $0$ is $L_{\text{\tiny
BEP}}$-optimal, violating calibration (Figure 2).

Moreover, as we illustrate in Figure 3(L), the link $\psi^{\infty}$ proposed
by Ramaswamy et al. can be recovered from Construction 1 by choosing the norm
$\|\cdot\|_{\infty}$ and $\epsilon=1/2$ (or smaller). Hence, our framework
could have simplified the process of finding $\psi^{\infty}$, and the
corresponding proof of consistency. It also could have simplified the
derivation of surrogate regret bounds (§ 4.3); we show how to recover the
tight bound of Ramaswamy et al. for the BEP surrogate in § C.2.

To illustrate these points further, consider the alternate link $\psi^{1}$ in
Figure 3(R), given by

$\psi^{1}(u)=\begin{cases}\bot&\|u\|_{1}\leq 1\\\
\varphi^{-1}(\operatorname*{sgn}(u))&\text{otherwise}\end{cases}~{}.$ (7)

This link is the result of Construction 1 for norm $\|\cdot\|_{1}$ and the
choice $\epsilon=1$, which proves calibration of $(L_{\text{\tiny
BEP}},\psi^{1})$ with respect to $\ell_{\text{abs}}$. Aside from its
simplicity, one possible advantage of $\psi^{1}$ is that it assigns $\bot$ to
much less of the surrogate space $\mathbb{R}^{d}$.

Figure 3: Designing links for $L_{\text{\tiny BEP}}$ with $d=2$ using
Construction 1. The embedding is shown in bold labeled by the corresponding
reports. (L) The link envelope $\Psi$ resulting from Construction 1 using
$\|\cdot\|_{\infty}$ and $\epsilon=1/2$, and a possible link $\psi$ which
matches eq. (6) from [44]. (M) An illustration of the thickened sets for two
sets $U,U^{\prime}\in\mathcal{U}$, using $\|\cdot\|_{1}$ and $\epsilon=1$. (R)
The envelope $\Psi$ and link $\psi$ using $\|\cdot\|_{1}$ and $\epsilon=1$.

###  5.3 Lovász hinge and the structured abstain problem

Many structured prediction settings can be thought of as making multiple
predictions at once, with a loss function that jointly measures error based on
the relationship between these predictions [29, 27, 41]. In the case of $k$
binary predictions, these settings are typically formalized by taking the
predictions and outcomes to be $\mathcal{R}=\mathcal{Y}=\\{-1,1\\}^{k}$, with
the $i$th coordinate giving the result for the $i$th binary prediction. A
natural family of losses are those which are functions of the misprediction or
disagreement set $\mathrm{dis}(r,y)=\\{i\in[k]\mid r_{i}\neq y_{i}\\}$,
meaning we may write $\ell^{f}(r)_{y}=f(\mathrm{dis}(r,y))$ for some set
function $f:2^{[k]}\to\mathbb{R}$. For example, Hamming loss is given by
$f(S)=|S|$. In an effort to provide a general convex surrogate for these
settings when $f$ is a submodular function, Yu and Blaschko [60] introduce the
_Lovász hinge_ surrogate $L^{f}:\mathbb{R}^{k}\to\mathbb{R}^{\mathcal{Y}}_{+}$
which leverages the well-known convex Lovász extension of submodular
functions. While the authors provide theoretical justification and
experiments, they leave open whether the Lovász hinge is actually consistent
for $\ell^{f}$.

Finocchiaro et al. [20] use our embedding framework to resolve the consistency
of $L^{f}$, showing that it is inconsistent with respect to $\ell^{f}$ outside
of the trivial case where $f$ is modular (in which case $\ell^{f}$ is a
weighted Hamming loss). Moreover, they show that $L^{f}$ embeds a variant
$\ell_{\text{abs}}^{f}$ of $\ell^{f}$ where one is allowed to abstain on a set
of indices $A\subseteq[k]$, which they call the _structured abstain problem_.
The inclusion of abstain options is natural when observing that the BEP
surrogate $L_{\text{\tiny BEP}}$, for multiclass classification with an abtain
option (§ 5.2), is the special case of $L^{f}$ where
$f(S)=\mathbbm{1}\\{S\neq\emptyset\\}$.

To derive the discrete loss $\ell_{\text{abs}}^{f}$ that $L^{f}$ embeds, the
authors follow an approach similar to § 5.1 to show that the set
$\mathcal{V}=\\{-1,0,1\\}^{k}$ is representative for $L^{f}$, for any choice
of $f$. From Proposition 1, they conclude that $L^{f}$ embeds
$\ell_{\text{abs}}^{f}:=L^{f}|_{\mathcal{V}}$. Letting
$\mathrm{abs}(v)=\\{i\in[k]\mid v_{i}=0\\}$ denote the “abstain” set, we may
write $\ell_{\text{abs}}^{f}:\mathcal{V}\to\mathbb{R}^{\mathcal{Y}}_{+}$ as

$\ell_{\text{abs}}^{f}(v)_{y}=f(\mathrm{dis}(v,y)\setminus\mathrm{abs}(v))+f(\mathrm{dis}(v,y))~{}.$
(8)

(Observe that $\mathrm{abs}(v,y)\subseteq\mathrm{dis}(v,y)$, since
$y\in\\{-1,1\\}^{k}$.) By Theorem 2, then, there is a link function such that
the Lovász hinge is consistent with respect to the structured abstain loss
$\ell_{\text{abs}}^{f}$.

As Finocchiaro et al. observe, actually determining a calibrated link function
in this case is nontrivial. Simple threshold links like for the BEP surrogate
in § 5.2 are not always calibrated, thus casting doubt that a trial-and-error
approach for finding the link would be successful. Instead, the authors
leverage our thickened link construction (Construction 1) to derive two links
$\psi^{*}$ and $\psi^{\diamond}$, which have somewhat intricate geometric
structure (Figure 4). Perhaps surprisingly, by deriving the link envelope
$\Psi$ which is contained in the envelopes for $L^{f}$ for all submodular and
increasing $f$, they prove that $\psi^{*}(u)\subseteq\Psi(u)$ and
$\psi^{\diamond}(u)\subseteq\Psi(u)$ for all $u\in\mathbb{R}^{d}$. Thus, both
$(L^{f},\psi^{*})$ and $(L^{f},\psi^{\diamond})$ are simultaneously calibrated
with respect to $\ell_{\text{abs}}^{f}$ for all such $f$.

Figure 4: Links $\psi^{*}$ and $\psi^{\diamond}$ such that $(L^{f},\psi^{*})$
and $\psi^{\diamond}$ are calibrated with respect to $\ell_{\text{abs}}^{f}$
for all suitable $f$. Points in each region link to the embedding point
contained in the region. Both are constructed via the link envelope $\Psi$
from Construction 1, which yields possible choices for calibrated links.

###  5.4 Embedding ordered partitions via Weston-Watkins hinge

As the hinge loss is one of the most common surrogates for binary support
vector machines (SVMs), original extensions to the multiclass setting included
a one-vs-all reduction to the binary problem via hinge loss, generating
${n\choose 2}$ hyperplanes for $n$ labels. Proposing a more efficient
solution, Weston and Watkins [56] give an alternate surrogate for multiclass
SVM prediction, defined as follows for predictions $u\in\mathbb{R}^{n}$,

$L_{\text{\tiny WW}}(u)_{y}=\sum_{i\in\mathcal{Y}:i\neq
y}(1-(u_{y}-u_{i}))_{+}~{}.$ (9)

This surrogate $L_{\text{\tiny WW}}$ was later shown to be inconsistent with
respect to 0-1 loss [54, 36].

Wang and Scott [55] use our embedding framework to show that the
Weston–Watkins hinge embeds the _ordered partition_ loss $\ell_{\text{\tiny
OP}}$, as defined below. In turn, they recover the result of inconsistency
with respect to 0-1 loss. The report space for $\ell_{\text{\tiny OP}}$ can be
defined in terms of nested subsets of $[n]:=\\{1,\ldots,n\\}$, as follows.
555To recover the partition of Wang and Scott [55], one can define
$S_{i}=T_{i}\setminus T_{i-1}$.

$\displaystyle\mathcal{T}=\\{(T_{0},\ldots,T_{s})\mid s\geq
1,\emptyset=T_{0}\subsetneq T_{1}\subsetneq\ldots\subsetneq T_{s}=[n]\\}~{}.$

The ordered partition target loss $\ell_{\text{\tiny
OP}}:\mathcal{T}\to\mathbb{R}^{\mathcal{Y}}_{+}$ is then defined

$\displaystyle\ell_{\text{\tiny OP}}(T)_{y}$
$\displaystyle=\sum_{i=1}^{s}\left(|T_{i}|\cdot\mathbbm{1}\\{y\not\in
T_{i-1}\\}\right)-1~{}.~{}$

The loss $\ell_{\text{\tiny OP}}$ can be interpreted as a variation of 0-1
loss incorporating confidence: reports are a nested sequence of sets, and the
penalty upon seeing label $y$ is the cardinality of the first set containing
$y$, plus the cardinality of all earlier sets.

Upon showing that $L_{\text{\tiny WW}}$ embeds $\ell_{\text{\tiny OP}}$, Wang
and Scott then characterize $\mathrm{prop}[\ell_{\text{\tiny OP}}]$. In the
same manner as Figure 2, knowledge of the level sets of
$\mathrm{prop}[\ell_{\text{\tiny OP}}]$ clarifies which label distributions
are the source of inconsistency for classification. Removing these
distributions gives a set $\mathcal{P}\subseteq\Delta_{\mathcal{Y}}$ such that
$L_{\text{\tiny WW}}$ and the canonical link $\psi(u):u\mapsto
r\in\operatorname*{arg\,max}_{y}\langle e_{y},u\rangle$ are calibrated with
respect to 0-1 loss on $\mathcal{P}\subseteq\Delta_{\mathcal{Y}}$ (i.e., such
that eq. (2) holds for all $p\in\mathcal{P}$). See Figure 5 for an
illustration.

Figure 5: Level sets of $\mathrm{prop}[\ell_{\text{\tiny OP}}]$ (solid lines)
juxtaposed against the level sets of $\mathrm{mode}$ (dashed lines). For the
same reason as in Figure 2, the level sets of $\mathrm{prop}[\ell_{\text{\tiny
OP}}]$ whose relative interiors span multiple cells of the mode, colored blue,
cannot be properly linked to the mode. These offending cells correspond to
reports whose highest partition has more than one element, where in the white
cells, the “highest” element of the partition is well-defined.

###  5.5 Surrogates for top-$k$ classification

In settings like object recognition and information retrieval, it is natural
to predict a set $S$ of labels. In top-$k$ classification, one requires
$|S|=k$, and given the true label $y$, the target loss is
$\ell^{\text{top-$k$}}(S)_{y}=\mathbbm{1}\\{y\notin S\\}$ [33, 34, 35, 59, 8,
45, 46]. In the literature on surrogates for top-$k$ classification, one goal
has been to find a surrogate satisfying the following three desiderata:
convexity, consistency, and piecewise linear (“hinge-like”) structure. Yang
and Koyejo [59] show that a number of previously proposed polyhedral losses,
i.e., those which are convex and hinge-like, are inconsistent. They further
suggest that perhaps no surrogate could satisfy all three properties.

Finocchiaro et al. [19] apply the general approach outlined above to each of
the polyhedral surrogates shown to be inconsistent by Yang and Koyejo, and
determine the target problems they do solve, i.e., the discrete losses they
embed. Each of the examined surrogates embeds a discrete loss which can be
viewed as a variant of the top-$k$ problem, allowing the algorithm to express
varying levels of “confidence” on the top $k$ labels or report fewer than $k$
labels. The label distributions for which these optimal reports differ from
the optimal top-$k$ reports are shown in Table 5.5 with $n=4$ and
$k\in\\{2,3\\}$. (Recall $n=|\mathcal{Y}|$, the number of labels.)

| $\mathrm{prop}[L^{(2)}]$ | $\mathrm{prop}[L^{(3)}]$ | $\mathrm{prop}[L^{(4)}]$ | $\mathrm{prop}[L^{k}]$
---|---|---|---|---
$k=2$ |  |  |  |

&

${p_{1}}$${p_{3}}$${p_{2}}$

${p_{1}}$${p_{3}}$${p_{2}}$$1,3$$\emptyset$$2$$14$

${p_{1}}$${p_{3}}$${p_{2}}$$14$$23$

$k=3$

${p_{1}}$${p_{3}}$${p_{2}}$

${p_{1}}$${p_{3}}$${p_{2}}$

${p_{1}}$${p_{3}}$${p_{2}}$$134$$234$$124$

${p_{1}}$${p_{3}}$${p_{2}}$$134$$234$$124$

Table 1:  Visualizations of the properties elicited by the losses (embedded
by) $L^{(2)}$, $L^{(3)}$, $L^{(4)}$ studied by Yang and Koyejo [59] and
Finocchiaro et al. [19], and $L^{k}$ in eq. (10). We take $n=4$ and
$k\in\\{2,3\\}$, and visualize in 2 dimensions by fixing $p_{4}=1/4$. The
blue-filled regions are cells of the surrogate property which cross the dashed
blue lines of the target property, exhibiting inconsistency (see Figure 2).
Intuitively, the inconsistency arises from ambiguity in the top-$k$ elements
of the optimal surrogate report.

For example, one of the surrogates is
$L^{(4)}(u)_{y}=\left(1-u_{y}+\frac{1}{k}\sum_{i=1}^{k}(u_{\setminus
y})_{[i]}\right)_{+}$, where $u_{[i]}$ denotes the $i$th largest element of
$u\in\mathbb{R}^{n}$. The authors show that $L^{(4)}$ embeds
$\ell^{(4)}(T)_{y}=\tfrac{k+1}{k+1-|T|}\mathbbm{1}\\{y\notin T\\}$, where $T$
is a set of at most $k$ labels. These embedded losses may therefore be useful
in top-$k$ settings where choosing smaller sets may have some benefit, such as
a search engine that can use unused space for advertisements. Using the losses
each proposed surrogate embeds, using the same technique from Figure 2, the
authors go on to derive constraints on the label distributions under which the
proposed surrogates are actually consistent for top-$k$ classification; these
constraints are tighter than previous constraints [59].

Beyond analyzing the previously proposed surrogates, Finocchiaro et al. also
use our framework to derive the first consistent polyhedral surrogate for
$\ell^{\text{top-$k$}}$,

$\displaystyle L^{k}(u)_{y}$
$\displaystyle=\max\left(u_{[1]},\max_{m\in\\{k+1,\ldots,n\\}}\left[1-\frac{k}{m}+\frac{1}{m}\sum_{i=1}^{m}u_{[i]}\right]\right)-u_{y}~{}.$
(10)

That is, they show that a hinge-like surrogate does exist which is both convex
and consistent. In light of our framework, this fact is unsurprising: Theorems
1 and 2 imply that _every_ discrete loss has a consistent polyhedral
surrogate. This new surrogate $L^{k}$ is given directly by the construction
from the proof of Theorem 4 and applying Theorem 2 to obtain consistency.
While Theorem 2 guarantees the existence of some consistent link function, the
authors further ask whether the canonical argmax link function $\psi^{k}$,
which returns the $k$ largest elements of $u$, is calibrated. They indeed
confirm its consistency using our framework, showing that $\psi^{k}$ is
$\epsilon$-separated for $L^{k}$ and $\ell^{\text{top-$k$}}$, for any
$\epsilon\leq\frac{1}{2n}$ [19, Theorem 4.4].

##  6 Additional Structure of Embeddings

We have shown in § 3 a close connection between embeddings and polyhedral
losses. Here we go beyond polyhedral losses, showing a more general necessary
condition for an embedding: a surrogate embeds a discrete loss if and only if
it has a polyhedral Bayes risk, or equivalently, a finite representative set
(Lemma 3). This result implies that the embedding condition simplifies to
matching Bayes risks (Proposition 2). We also use this result to understand
deeper structure of embeddings, and the geometry of the underlying properties.
In particular, we study a natural notion of a “trimmed” loss function
(Definition 9), and connect this notion to tight embeddings, and to non-
redundancy from property elicitation (Proposition 3).

###  6.1 Structure of polyhedral Bayes risks

While we have focused on polyhedral losses thus far, many of our results
extend to losses with polyhedral Bayes risks, a strictly weaker condition. (We
say a concave function is polyhedral if its negation is a polyhedral convex
function.) To see that every polyhedral loss has a polyhedral Bayes risk,
recall that Theorem 3 constructs a finite representative set $\mathcal{S}$ for
any polyhedral loss $L$, and thus $\underline{L}=\underline{L|_{\mathcal{S}}}$
by Lemma 1, which is polyhedral. Conversely, however, a Bayes risk may be
polyhedral even if the loss itself is not. For example, a modified hinge loss
$L(r)_{y}=\max(r^{2}-1,1-ry)$ as shown in Figure 6, which matches hinge loss
on the interval $[-1,1]$ but is strictly convex outside the interval $[-2,2]$,
still embeds twice 0-1 loss.

Much of our embedding framework relies on the existence of finite
representative sets. Our main structural result is that a minimizable loss has
a finite representative sets if and only if its Bayes risk is polyhedral. The
proof looks at the facets (full-dimensional faces) of the Bayes risk, and
argues that each facet is generated by the loss at a particular report, and
the (finite) set of these reports is representative. Along the way, we
identify several other useful facts deriving from this same geometry; for
example, a discrete loss tightly embedded by a loss are unique up to
relabeling, any set-wise minimal representative set must be minimum in
cardinality, and the level sets of the corresponding property are unique and
full-dimensional. Together, these facts form Lemma 3, which we use throughout
this section. See § E for ommitted proofs.

Figure 6: (L) Expected modified hinge loss for fixed distribution; (R) Bayes
risk of modified hinge still matches the Bayes risk of hinge.

######  Lemma 3.

Let $L:\mathcal{R}\to\mathbb{R}^{\mathcal{Y}}_{+}$ be a minimizable loss with
a polyhedral Bayes risk $\underline{L}$. Then $L$ has a finite representative
set. Furthermore, letting $\Gamma=\mathrm{prop}[L]$, there exist finite sets
$\mathcal{V}\subseteq\mathbb{R}^{\mathcal{Y}}_{+}$ and
$\Theta=\\{\theta_{v}\subseteq\Delta_{\mathcal{Y}}\mid v\in\mathcal{V}\\}$,
both uniquely determined by $\underline{L}$ alone, such that

  1. 1.

A set $\mathcal{R}^{\prime}\subseteq\mathcal{R}$ is representative if and only
if $\mathcal{V}\subseteq L(\mathcal{R}^{\prime})$.

  2. 2.

A set $\mathcal{R}^{\prime}\subseteq\mathcal{R}$ is minimum representative if
and only if $L(\mathcal{R}^{\prime})=\mathcal{V}$.

  3. 3.

A set $\mathcal{R}^{\prime}\subseteq\mathcal{R}$ is representative if and only
if $\Theta\subseteq\\{\Gamma_{r}\mid r\in\mathcal{R}^{\prime}\\}$.

  4. 4.

A set $\mathcal{R}^{\prime}\subseteq\mathcal{R}$ is minimum representative if
and only if $\\{\Gamma_{r}\mid r\in\mathcal{R}^{\prime}\\}=\Theta$.

  5. 5.

Every representative set for $L$ contains a minimum representative set for
$L$.

  6. 6.

The set of full-dimensional level sets of $\Gamma$ is exactly $\Theta$.

  7. 7.

For any $r\in\mathcal{R}$, there exists $\theta\in\Theta$ such that
$\Gamma_{r}\subseteq\theta$.

  8. 8.

$L$ tightly embeds $\ell:\mathcal{R}^{\prime}\to\mathbb{R}^{\mathcal{Y}}_{+}$
if and only if $\ell$ is injective and
$\ell(\mathcal{R}^{\prime})=\mathcal{V}$.

As a finite representative set implies a polyhedral Bayes risk by Lemma 1,
Lemma 3 shows that polyhedral Bayes risks are equivalent to having finite
representative sets, which in turn gives an embedding by Proposition 1.

######  Corollary 1.

The following are equivalent for any minimizable loss
$L:\mathcal{R}\to\mathbb{R}^{\mathcal{Y}}_{+}$.

  1. 1.

$\underline{L}$ is polyhedral.

  2. 2.

$L$ has a finite representative set.

  3. 3.

$L$ embeds a discrete loss.

From Corollary 1, $L$ having a finite representative set is an equivalent
condition to $L$ being minimizable and $\underline{L}$ being polyhedral.
(Recall that having a finite representative set already implies
minimizability.) As it is also a more succinct condition, we will use the
former in the sequel. In particular, the implications of Lemma 3 follow
whenever $L$ has a finite representative set.

###  6.2 Equivalent condition: matching Bayes risks

Lemma 3 leads to another appealing equivalent condition to an embedding: a
surrogate embeds a discrete loss if and only if their Bayes risks match. The
proof follows by mapping the two conditions of an embedding onto the geometric
structure revealed by Lemma 3: (ii) if the properties have the same level
sets, the Bayes risks have the same projections onto $\Delta_{\mathcal{Y}}$,
and (i) if the loss values match, then the slopes of the Bayes risk must be
identical as well.

######  Proposition 2.

Let discrete loss $\ell$ and minimizable loss $L$ be given. Then $L$ embeds
$\ell$ if and only if $\underline{L}=\underline{\ell}$.

###### Proof.

Define $\Gamma=\mathrm{prop}[L]$ and $\gamma=\mathrm{prop}[\ell]$.

Suppose $L$ embeds $\ell$, so we have some $\mathcal{S}\subseteq\mathcal{R}$
which is representative for $\ell$ and an embedding
$\varphi:\mathcal{S}\to\mathbb{R}^{d}$; take
$\mathcal{U}:=\varphi(\mathcal{S})$. Since $\mathcal{S}$ is representative for
$\ell$, by embedding condition (ii) we have $\\{\gamma_{s}\mid
s\in\mathcal{S}\\}=\\{\Gamma_{u}\mid u\in\mathcal{U}\\}$, so $\mathcal{U}$ is
representative for $L$. By Lemma 1, we have
$\underline{\ell}=\underline{\ell|_{\mathcal{S}}}$ and
$\underline{L}=\underline{L|_{\mathcal{U}}}$. As
$L(\varphi(\cdot))=\ell(\cdot)$ by embedding condition (i), for all
$p\in\Delta_{\mathcal{Y}}$ we have

$\underline{\ell}(p)=\underline{\ell|_{\mathcal{S}}}(p)=\min_{r\in\mathcal{S}}\langle
p,\ell(r)\rangle=\min_{r\in\mathcal{S}}\langle
p,L(\varphi(r))\rangle=\min_{u\in\mathcal{U}}\langle
p,L(u)\rangle=\underline{L|_{\mathcal{U}}}(p)=\underline{L}(p)~{}.$

For the reverse implication, assume $\underline{L}=\underline{\ell}$, which
are polyhedral functions as $\ell$ is discrete. From Lemma 3(2), we have some
set $\mathcal{V}\subseteq\mathbb{R}^{\mathcal{Y}}_{+}$ and minimum
representative sets $\mathcal{R}^{*}\subseteq\mathcal{R}$ and
$\mathcal{U}^{*}\subseteq\mathcal{U}$, for $\ell$ and $L$ respectively, such
that $\ell(\mathcal{R}^{*})=\mathcal{V}=L(\mathcal{U}^{*})$. As
$\mathcal{R}^{*}$ and $\mathcal{U}^{*}$ are miniumum, they cannot repeat loss
vectors, and thus $|\mathcal{R}^{*}|=|\ell(\mathcal{R}^{*})|$ and
$|L(\mathcal{U}^{*})|=|\mathcal{U}^{*}|$. We conclude that $\mathcal{R}^{*}$
and $\mathcal{U}^{*}$ are both in bijection with $\mathcal{V}$. The map
$\varphi:\mathcal{R}^{*}\to\mathbb{R}^{d}$, given by
$\varphi(r)=u\in\mathcal{U}^{*}$ where $\ell(r)=L(u)$, is therefore well-
defined. Condition (i) of an embedding is immediate. From Proposition 1,
$\ell$ embeds $\ell|_{\mathcal{R}^{*}}$ and $L$ embeds $L|_{\mathcal{U}^{*}}$,
both via the identity embedding. Using condition (ii) from both embeddings,
for all $p\in\Delta_{\mathcal{Y}}$ and $r\in\mathcal{R}^{*}$, we have

$r\in\gamma(p)\iff
r\in\mathrm{prop}[\ell|_{\mathcal{R}^{*}}](p)\iff\varphi(r)\in\mathrm{prop}[L|_{\mathcal{U}^{*}}](p)\iff\varphi(r)\in\mathrm{prop}[L](p)~{},$

giving condition (ii). ∎

We use this fact in the proof of Theorem 4 to show that every discrete loss is
embedded by some polyhedral surrogate. See Figure 1 for an illustration.

###  6.3 Trimming a loss

Central to the structural results in Lemma 3 is the existence of a canonical
set of loss vectors $\mathcal{V}$ which match the loss vectors of any minimum
representative set. This fact may seem surprising when one considers that
losses may have many mimimum representative sets. For example, consider hinge
loss with a spurious extra dimension, i.e.,
$L:\mathbb{R}^{2}\to\mathbb{R}^{\mathcal{Y}}$,
$L((r_{1},r_{2}))_{y}=\max(0,1-r_{1}y)$ for $\mathcal{Y}=\\{-1,+1\\}$. Here
the minimum representative sets are exactly the two-element sets of the form
$\\{(-1,a),(1,b)\\}$ for any $a,b\in\mathbb{R}$. Lemma 3(2) states that, while
the minimum representative set is not unique, its loss vectors are.

Motivated by this observation, let us define the “trim” of a loss to be this
unique set $\mathcal{V}$ of loss vectors induced by any minimum representative
set, which again is well-defined by Lemma 3(2).

######  Definition 9 (Trim).

Given a loss $L:\mathcal{R}\to\mathbb{R}_{+}^{\mathcal{Y}}$ with a finite
representative set, we define $\mathrm{trim}(L)=\\{L(r)\mid
r\in\mathcal{R}^{*}\\}$ given any minimum representative set $\mathcal{R}^{*}$
for $L$.

Using this notion of trimming a loss, we can again recast our embedding
condition: a loss embeds another if and only if they induce the same loss
vectors, or have the same $\mathrm{trim}$.

######  Proposition 3.

Let $L:\mathbb{R}^{d}\to\mathbb{R}^{\mathcal{Y}}_{+}$ have a finite
representative set, and let $\ell:\mathcal{R}\to\mathbb{R}^{\mathcal{Y}}_{+}$
be a discrete loss. Then $L$ embeds $\ell$ if and only if
$\mathrm{trim}(L)=\mathrm{trim}(\ell)$. Furthermore, $L$ tightly embeds $\ell$
if and only if $\ell$ is injective and $\mathrm{trim}(L)=\ell(\mathcal{R})$.

###### Proof.

As $L$ has a finite representative set, it is minimizable. Proposition 2 gives
$L$ embeds $\ell$ if and only if $\underline{L}=\underline{\ell}$. If
$\underline{L}=\underline{\ell}$, Lemma 3(2) gives
$\mathrm{trim}(L)=\mathrm{trim}(\ell)$. For the converse, suppose
$\mathrm{trim}(L)=\mathrm{trim}(\ell)=:\mathcal{V}$. Define the discrete loss
$\ell_{\mathrm{trim}}:\mathcal{V}\to\mathcal{V},v\mapsto v$. Then
$\ell_{\mathrm{trim}}$ is injective and
$\ell_{\mathrm{trim}}(\mathcal{V})=\mathcal{V}$, so from Lemma 3(8), both $L$
and $\ell$ tightly embed $\ell_{\mathrm{trim}}$. We conclude
$\underline{L}=\underline{\ell_{\mathrm{trim}}}=\underline{\ell}$ from
Proposition 2. The second statement also follows directly from Lemma 3(8). ∎

In a strong sonse, the trim operation reduces a loss to its core: the unique
minimal set of loss vectors that drive its statistical behavior. One can
therefore think of designing consistent convex surrogates as trying to “fill
out” this minimal set with additional loss vectors so that one attains
convexity while keeping trim the same.

###  6.4 Minimum representative sets and non-redundancy

The condition that a representative set be minimum implies that one has
identified exactly the “active” reports of a loss, in some sense. We now
relate this condition to another natural notion from the property elicitation
literature: non-redundancy [21, 31]. Intuitively, a loss is non-redundant if
no report is weakly dominated by another report.

######  Definition 10 (Non-redundancy).

A loss $L:\mathcal{R}\to\mathbb{R}^{\mathcal{Y}}_{+}$ eliciting
$\Gamma:\Delta_{\mathcal{Y}}\rightrightarrows\mathcal{R}$ is _redundant_ if
there are reports $r,r^{\prime}\in\mathcal{R}$ with $r\neq r^{\prime}$ such
that $\Gamma_{r}\subseteq\Gamma_{r^{\prime}}$, and _non-redundant_ otherwise.

From the structural result of Lemma 3, we can see that in fact these two
notions are equivalent when $L$ has a polyhedral Bayes risk.

######  Proposition 4.

Let $L:\mathcal{R}\to\mathbb{R}^{\mathcal{Y}}_{+}$ have a finite
representative set $\mathcal{R}^{\prime}$. Then $\mathcal{R}^{\prime}$ is a
minimum representative set for $L$ if and only if $L|_{\mathcal{R}^{\prime}}$
is non-redundant.

###### Proof.

Let $\Gamma=\mathrm{prop}[L]$. Suppose first that $L|_{\mathcal{R}^{\prime}}$
is redundant. Then there exist $r,r^{\prime}\in\mathcal{R}^{\prime}$ such that
$\Gamma_{r}\subseteq\Gamma_{r^{\prime}}$. Thus, for all $p\in\Gamma_{r}$, we
have $\\{r,r^{\prime}\\}\subseteq\Gamma(p)$. Therefore
$\mathcal{R}^{\prime}\setminus\\{r\\}$ still a representative set, so
$\mathcal{R}^{\prime}$ is not minimum.

Now suppose $L|_{\mathcal{R}^{\prime}}$ is non-redundant. As
$\mathcal{R}^{\prime}$ is a representative set, Lemma 3(5) gives some minimum
representative set $\mathcal{S}\subseteq\mathcal{R}^{\prime}$. Suppose we had
some $r\in\mathcal{R}^{\prime}\setminus\mathcal{S}$. Now Lemma 3(4,7) gives
some $s\in\mathcal{S}$ such that $\Gamma_{r}\subseteq\Gamma_{s}$, which
contradicts $L|_{\mathcal{R}^{\prime}}$ being non-redundant. We conclude
$L(\mathcal{S})=L(\mathcal{R}^{\prime})$, meaning $\mathcal{R}^{\prime}$ is a
minimum representative set. ∎

######  Corollary 2.

Let loss $L:\mathcal{R}\to\mathbb{R}^{\mathcal{Y}}_{+}$ with finite
representative set $\mathcal{R}^{\prime}$ be given. Then $L$ tightly embeds
$L|_{\mathcal{R}^{\prime}}$ if and only if $L|_{\mathcal{R}^{\prime}}$ is non-
redundant.

In fact, we can show something stronger: the reports in minimum representative
sets are precisely those which are not strictly redundant. To formalize this
statement, given $\Gamma:\Delta_{\mathcal{Y}}\rightrightarrows\mathcal{R}$,
let $\mathrm{red}(\Gamma):=\\{r\in\mathcal{R}\mid\exists
r^{\prime}\in\mathcal{R},\;\Gamma_{r}\subsetneq\Gamma_{r^{\prime}}\\}$ be the
set of strictly redundant reports. Similarly, for minimizable $L$, let
$\mathrm{red}(L):=\mathrm{red}(\mathrm{prop}[L])$.

######  Proposition 5.

Let $L:\mathcal{R}\to\mathbb{R}^{\mathcal{Y}}_{+}$ have a finite
representative set. Let $\mathcal{R}^{\prime}$ be the union of all minimum
representative sets for $L$. Then
$\mathcal{R}^{\prime}=\mathcal{R}\setminus\mathrm{red}(L)$.

###### Proof.

Let $\Gamma=\mathrm{prop}[L]$. Let $\mathcal{S}$ be a minimum representative
set for $L$, and let $s\in\mathcal{S}$. Suppose for a contradiction that
$s\in\mathrm{red}(\Gamma)$. Then we have some $r\in\mathcal{R}$ with
$\Gamma_{s}\subsetneq\Gamma_{r}$. From Lemma 3(4,7) we have some
$s^{\prime}\in\mathcal{S}$ such that $\Gamma_{r}\subseteq\Gamma_{s^{\prime}}$.
But now $\Gamma_{s}\subsetneq\Gamma_{r}\subseteq\Gamma_{s^{\prime}}$,
contradicting $\mathcal{S}$ being minimum representative. Thus
$\mathcal{S}\subseteq\mathcal{R}\setminus\mathrm{red}(\Gamma)$.

For the reverse inclusion, let $r\in\mathcal{R}\setminus\mathrm{red}(\Gamma)$.
Let $\mathcal{S}$ again be a minimum representative set for $L$. From Lemma
3(4,7), we have some $s\in\mathcal{S}$ such that
$\Gamma_{r}\subseteq\Gamma_{s}$. By definition of $\mathrm{red}(L)$, we
conclude $\Gamma_{r}=\Gamma_{s}$. Now take
$\mathcal{S}^{\prime}=(\mathcal{S}\setminus\\{s\\})\cup\\{r\\}$, that is, the
same set of reports with $r$ replacing $s$. We have $\\{\Gamma_{s}\mid
s\in\mathcal{S}\\}=\\{\Gamma_{s^{\prime}}\mid
s^{\prime}\in\mathcal{S}^{\prime}\\}$, and thus $\mathcal{S}^{\prime}$ is a
minimum representative for $L$ by Lemma 3(4). As $r\in\mathcal{S}^{\prime}$,
we have $r\in\mathcal{R}^{\prime}$ and we are done. ∎

As a corollary, we can state another characterization of $\mathrm{trim}$ in
terms of redundant reports. The result follows immediately from the definition
of $\mathrm{trim}$.

######  Corollary 3.

Let $L:\mathcal{R}\to\mathbb{R}^{\mathcal{Y}}_{+}$ have a finite
representative set. Then
$\mathrm{trim}(L)=L(\mathcal{R}\setminus\mathrm{red}(L))$.

This result motivates the analogous definition for properties,
$\mathrm{trim}(\Gamma):=\\{\Gamma_{r}\mid
r\in\mathcal{R}\setminus\mathrm{red}(\Gamma)\\}$. We leverage this definition
next, to study embeddings at the property level.

###  6.5 A property elicitation perspective on trimmed losses

We conclude this section with a structural result similar to Lemma 3, but for
properties. To do so, we must first generalize the definition of embeddeding
to properties. We say a property
$\Gamma:\Delta_{\mathcal{Y}}\rightrightarrows\mathbb{R}^{d}$ embeds a finite
property $\gamma:\Delta_{\mathcal{Y}}\rightrightarrows\mathcal{R}$ if
condition (ii) of Definition 7 holds. In other words, $\Gamma$ embeds $\gamma$
if we have some representative set $\mathcal{S}\subseteq\mathcal{R}$ for
$\gamma$ and embedding $\varphi:\mathcal{S}\to\mathbb{R}^{d}$ such that for
all $s\in\mathcal{S}$ we have $\gamma_{s}=\Gamma_{\varphi(s)}$.

Roughly, our result is as follows. First, if $\Gamma$ embeds $\gamma$, the
level sets of $\Gamma$ must all be redundant relative to $\gamma$. In other
words, $\Gamma$ is exactly the property $\gamma$ up to relabelling reports,
but potentially with other reports “filling in the gaps” between the embedded
reports of $\gamma$. When working with convex surrogates, extra reports often
arise in the convex hull of the embedded reports. In this sense, we can regard
embedding as only a slight departure from direct elicitation: if a loss $L$
directly elicits $\Gamma$ which embeds $\gamma$, we can almost think of $L$ as
eliciting $\gamma$ itself. Finally, we have an important converse: if $\Gamma$
has finitely many full-dimensional level sets, or equivalently, if
$\mathrm{trim}(\Gamma)$ is finite, then $\Gamma$ must embed some finite
elicitable property with the same full-dimensional level sets.

The proof relies heavily on Lemma 3. The statements about level sets use the
following corollary of Proposition 3 for properties.

######  Corollary 4.

Let $\Gamma:\Delta_{\mathcal{Y}}\rightrightarrows\mathcal{R}$ be an elicitable
property with a finite representative set. Then $\mathrm{trim}(\Gamma)$ is the
set of full-dimensional level sets of $\Gamma$.

###### Proof.

Let $L$ elicit $\Gamma$. From Lemma 3(4,6), for any finite minumum
representative set $\mathcal{S}\subseteq\mathcal{R}$, the set
$\\{\Gamma_{s}\mid s\in\mathcal{S}\\}$ is exactly the set of full-dimensional
level sets $\Theta$ of $\Gamma$. From Proposition 4, we have
$r\in\mathcal{R}\setminus\mathrm{red}(\Gamma)$ if and only if $r$ is an
element of some minimum representative set. As $\Gamma$ has at least one
minimum representative set, we conclude
$\mathrm{trim}(\Gamma)=\\{\Gamma_{r}\mid
r\in\mathcal{R}\setminus\mathrm{red}(\Gamma)\\}=\Theta$. ∎

######  Proposition 6.

Let $\Gamma:\Delta_{\mathcal{Y}}\rightrightarrows\mathbb{R}^{d}$ be an
elicitable property. The following are equivalent:

  1. 1.

$\Gamma$ embeds a elicitable finite property
$\gamma:\Delta_{\mathcal{Y}}\rightrightarrows\mathcal{R}$.

  2. 2.

$\mathrm{trim}(\Gamma)$ is a finite set.

  3. 3.

There is a finite minimum representative set $\mathcal{U}$ for $\Gamma$.

  4. 4.

There is a finite set of full-dimensional level sets $\hat{\Theta}$ of
$\Gamma$, and $\cup\,\hat{\Theta}=\Delta_{\mathcal{Y}}$.

Moreover, when any of the above hold,
$\mathrm{trim}(\gamma)=\mathrm{trim}(\Gamma)=\\{\Gamma_{u}\mid
u\in\mathcal{U}\\}=\hat{\Theta}$.

###### Proof.

Let $L$ be a fixed loss eliciting $\Gamma$, so that in particular
$\underline{L}$ is fixed. By definition of elicitable properties, $L$ is
minimizable. In each case, we will show that $\underline{L}$ is polyhedral (or
equivalently, that $L$ has a finite representative set), and thus Lemma 3 will
give us the set $\Theta$ of full-dimensional level sets of $\Gamma$, uniquely
determined by $\underline{L}$. We will prove $1\Rightarrow 2\Rightarrow
3\Rightarrow 4\Rightarrow 1$, and in each case show that the relevant set of
level sets is equal to $\Theta$, giving the result.

$1\Rightarrow 2$: Let $\mathcal{S}$ be the representative set for $\gamma$ and
$\varphi:\mathcal{S}\to\mathbb{R}^{d}$ the embedding. Since $\mathcal{S}$ is
finite, $\varphi(\mathcal{S})$ is a finite representative set for $\Gamma$
(and $L$; thus, $\underline{L}$ is polyhedral). Corollary 4 now gives
$\mathrm{trim}(\Gamma)=\Theta$, which is finite, showing Case 2.

$2\Rightarrow 3$: If $\mathrm{trim}(\Gamma)$ is finite, then in particular we
have a finite set of reports $\mathcal{S}\subseteq\mathbb{R}^{d}$ such that
$\mathrm{trim}(\Gamma)=\\{\Gamma_{s}\mid s\in\mathcal{S}\\}$. As $\Gamma$ is
elicitable, $\mathbb{R}^{d}$ is representative for $\Gamma$. By definition of
$\mathrm{trim}$, we have
$\Delta_{\mathcal{Y}}=\cup_{r\in\mathbb{R}^{d}}\Gamma_{r}=\cup\mathrm{trim}(\Gamma)=\cup_{s\in\mathcal{S}}\Gamma_{s}$,
and therefore $\mathcal{S}$ is representative for $\Gamma$ and for $L$. As
$\mathcal{S}$ is finite, we have $\underline{L}$ polyhedral. From Lemma 3(5),
we have some minimum representative set $\mathcal{U}\subseteq\mathcal{S}$ for
$L$ and $\Gamma$, implying statement 3. Moreover, Lemma 3(4,6) gives
$\\{\Gamma_{u}\mid u\in\mathcal{U}\\}=\Theta$.

$3\Rightarrow 4$: Let $\mathcal{U}$ be a finite minimum representative set for
$\Gamma$. Then $\underline{L}=\underline{L|_{\mathcal{U}}}$ is polyhedral.
Lemma 3(4,6) once again gives $\\{\Gamma_{u}\mid u\in\mathcal{U}\\}=\Theta$.
We simply let $\hat{\Theta}=\Theta$, giving statement 4 as $\mathcal{U}$ is
representative.

$4\Rightarrow 1$: Let $\mathcal{S}\subseteq\mathcal{R}$ such that
$\\{\Gamma_{s}\mid s\in\mathcal{S}\\}=\hat{\Theta}$. Then $\mathcal{S}$ is
representative for $\Gamma$ and $L$, as
$\cup\hat{\Theta}=\Delta_{\mathcal{Y}}$. Again, this yields a finite
representative set for $L$. Lemma 1 now states that $L$ embeds
$L|_{\mathcal{S}}$, so $\Gamma$ embeds $\gamma:=\Gamma|_{\mathcal{S}}$, giving
Case 1. Finally, Corollary 4 gives $\mathrm{trim}(\gamma)=\Theta$. ∎

As a final observation, recall that a property $\Gamma$ elicited by a
polyhedral loss has a finite range, in the sense that there are only finitely
many optimal sets $\Gamma(p)$ for $p\in\Delta_{\mathcal{Y}}$ (Lemma 2).
Proposition 6 shows a complementary statement: there are only finitely many
level sets $\Gamma_{u}$ for $u\in\mathbb{R}^{d}$. In other words, both
$\Gamma$ and $\Gamma^{-1}$ have a finite range as multivalued maps.

##  7 Polyhedral Indirect Elicitation Implies Consistency

As we have observed, consistency, and therefore calibration, implies indirect
elicitation (§ 2.3). In general, indirect elicitation is simpler and weaker
than calibration, since it only depends on the loss through the property it
elicits, i.e., its exact minimizers. Surprisingly, for polyhedral surrogates,
we show the converse: indirect elicitation implies calibration, and therefore
consistency.

######  Theorem 8.

Let $L:\mathbb{R}^{d}\to\mathbb{R}^{\mathcal{Y}}_{+}$ be a polyhedral loss
which indirectly elicits a finite property $\gamma$. For any loss $\ell$
eliciting $\gamma$, there exists a link $\psi$ such that $(L,\psi)$ is
calibrated with respect to $\ell$.

One technical detail is that the link function may have to change. That is, we
will show that if $(L,\psi)$ indirectly elicits $\mathrm{prop}[\ell]$, then
there exists some potentially different link $\psi^{\prime}$ such that
$(L,\psi^{\prime})$ is calibrated with respect to $\ell$. To see why this
change may be necessary, consider again the example from § 2.3: hinge loss
with the link $\psi(u)=-1$ for $u<1$ and $\psi(u)=1$ for $u\geq 1$. Here
indirect elicitation is achieved, since we have $\psi((-\infty,-1])=\\{-1\\}$
and $\psi([1,\infty))=\\{1\\}$, but the link is not $\epsilon$-separated for
any $\epsilon>0$. In general, it is not clear whether one can always adjust
the link in this case to achieve separation, and therefore calibration.
Fortunately, for polyhedral surrogates, one can always “thicken” a given link
to achieve separation.

We give two proofs of Theorem 8. The first is direct: we show, as foreshadowed
in § 4, that our thickened link construction can be generalized for indirect
elicitation. In fact, we will further prove that our general construction
recovers every possible calibrated link function. The second proof highlights
the central role that embeddings play when reasoning about polyhedral
surrogates. Specifically, we will show that if a polyhedral surrogate
indirectly elicits a finite property, the link function must “pass through” an
embedding, giving calibration through Construction 1.

###  7.1 Generalizing the thickened link construction

Given that Construction 1 uses the embedding
$\varphi:\mathcal{S}\to\mathbb{R}^{d}$ in a crucial role, it is not
immediately clear how to generalize the construction beyond embeddings.
Specifically, this crucial role is in the definition of $R_{U}$, the set of
target reports which must be optimal whenever a given surrogate report set
$U\subseteq\mathbb{R}^{d}$ is optimal. Using the embedding, we can simply
define $R_{U}=\\{r\in\mathcal{S}\mid\varphi(r)\in U\\}$, since the definition
of embedding means that those are exactly the target reports (among the
representative set $\mathcal{S}$) which are optimal when $U$ is.

Now suppose we merely know that $L$ indirectly elicits some finite property
$\gamma:\Delta_{\mathcal{Y}}\rightrightarrows\mathcal{R}$. In § D, we give
Construction 2, which is the same as Construction 1 but with the following
modification of $R_{U}$ to $\hat{R}_{U}$. Let $\Gamma=\mathrm{prop}[L]$ and
$\mathcal{U}=\\{\Gamma(p)\mid p\in\Delta_{\mathcal{Y}}\\}$ as before. Then for
all $U\in\mathcal{U}$, we define
$\hat{R}_{U}:=\\{r\in\mathcal{R}\mid\Gamma_{U}\subseteq\gamma_{r}\\}$, where
$\Gamma_{U}:=\\{p\in\Delta_{\mathcal{Y}}\mid U=\Gamma(p)\\}$ is the set of
distributions for which $U$ is the surrogate optimal set. In words,
$\hat{R}_{U}$ is the set of reports $r$ which may be linked to from points in
$U$, in the sense that $U$ being $L$-optimal implies $r$ is $\ell$-optimal.
For the special case where $L$ embeds $\ell$, it is straightforward to verify
that $R_{U}=\hat{R}_{U}\cap\mathcal{S}$. As a result, Construction 1 is the
special case of Construction 2 where one is given an embedding and restricts
to the representative set $\mathcal{S}$ (Lemma 10).

The main result of § D is that, if a polyhedral surrogate indirectly elicits a
finite property, then for small enough $\epsilon>0$, Construction 2 always
produces a link (Proposition 8). Combined with the fact that, by design, the
construction and our choice of $\hat{R}_{U}$ enforce separation, we have the
following.

######  Proposition 7.

Let $L$ be a polyhedral surrogate which indirectly elicits a finite property
$\gamma$. Then there exists $\epsilon_{0}>0$ such that for all
$0<\epsilon\leq\epsilon_{0}$, Construction 2 for
$L,\gamma,\epsilon,\|\cdot\|_{\infty}$ produces a separated link from
$\mathrm{prop}[L]$ to $\gamma$.

Since separation is equivalent to calibration for polyhedral surrogates
(Theorem 5), we now have Theorem 8: indirect elicitation implies calibration
for polyhedral surrogates.

In fact, we can show something stronger: $\hat{R}_{U}$ enforces separation
exactly, and therefore every possible calibrated link must arise from
Construction 2.

######  Theorem 9.

A link $\psi$ is calibrated for a given polyhedral surrogate $L$ and discrete
target $\ell$ if and only if there exists $\epsilon>0$ such that $\psi$ is
produced by Construction 2 for $L,\mathrm{prop}[\ell],\epsilon,\|\cdot\|$.

###  7.2 Centrality of embeddings

To derive another proof of Theorem 8, we now show that, for polyhedral
surrogates, indirect elicitation must always pass through an embedding. That
is, if $L$ indirectly elicits $\gamma$, then there is some loss $\ell$ which
$L$ embeds, such that $\ell$ indirectly elicits $\gamma$. This result holds
more generally whenever $L$ has a finite representative set, as in § 6.

######  Lemma 4.

Let $L:\mathbb{R}^{d}\to\mathbb{R}^{\mathcal{Y}}_{+}$ be polyhedral. Then $L$
indirectly elicits a property $\gamma$ if and only if $L$ tightly embeds a
discrete loss $\ell$ that indirectly elicits $\gamma$.

###### Proof.

Let $\Gamma=\mathrm{prop}[L]$. From Lemma 3(8), $L$ tightly embeds a discrete
loss. Furthermore, Lemma 3(4,7,8) implies that $L$ indirectly elicits
$\hat{\gamma}:=\mathrm{prop}[\ell]$ for any discrete loss $\ell$ that $L$
tightly embeds. The link is any function $\hat{\psi}:u\mapsto r$ such that
$\Gamma_{u}\subseteq\hat{\gamma}_{r}$ for all $u\in\mathbb{R}^{d}$.

We will prove the stronger statement that, for any property $\gamma$, and any
loss $\ell:\mathcal{R}\to\mathbb{R}^{\mathcal{Y}}_{+}$ that $L$ tightly
embeds, $L$ indirectly elicits $\gamma$ if and only if $\ell$ indirectly
elicits $\gamma$. If $\ell$ indirectly elicits $\gamma$ via the link $\psi$,
then $L$ indirectly elicits $\gamma$ by transitivity of subset inclusion, as
$\Gamma_{u}\subseteq\hat{\gamma}_{\hat{\psi}(u)}\subseteq\gamma_{\psi\circ\hat{\psi}(u)}$
for all $u\in\mathbb{R}^{d}$. Conversely, suppose $L$ indirectly elicits
$\gamma$ via the link $\psi$. As $L$ tightly embeds $\ell$, from Lemma 3(4,8),
the level sets of $\hat{\gamma}$ are contained in the set $\\{\Gamma_{u}\mid
u\in\mathbb{R}^{d}\\}$. Letting the map
$\hat{\psi}:\mathcal{R}\to\mathbb{R}^{d}$ exhibit this contaiment, we have
$\hat{\gamma}_{r}=\Gamma_{\hat{\psi}(r)}\subseteq\gamma_{\psi\circ\hat{\psi}(r)}$
for all $r\in\mathcal{R}$. ∎

###### Alternate proof of Theorem 8.

Let $\mathcal{R}$ be the range of $\gamma$, so that
$\gamma:\Delta_{\mathcal{Y}}\rightrightarrows\mathcal{R}$, and let $\ell$
elicit $\gamma$. By Lemma 4, $L$ tightly embeds a discrete loss
$\hat{\ell}:\hat{\mathcal{R}}\to\mathbb{R}^{\mathcal{Y}}_{+}$ such that
$\hat{\ell}$ indirectly elicits $\gamma$; let
$\psi^{\mathcal{R}}:\hat{\mathcal{R}}\to\mathcal{R}$ be the corresponding link
function. Let $\hat{\gamma}:=\mathrm{prop}[\hat{\ell}]$ be the property that
$\hat{\ell}$ directly elicits. Then for all $r\in\hat{\mathcal{R}}$ and
$p\in\Delta_{\mathcal{Y}}$ we have
$r\in\hat{\gamma}(p)\implies\psi^{\mathcal{R}}(r)\in\gamma(p)$. Moreover,
Construction 1 gives a link function
$\hat{\psi}:\mathbb{R}^{d}\to\hat{\mathcal{R}}$ such that $(L,\hat{\psi})$ is
calibrated with respect to $\hat{\ell}$.

Consider $\psi:=\psi^{\mathcal{R}}\circ\hat{\psi}$ and fix
$p\in\Delta_{\mathcal{Y}}$. For any $u\in\mathbb{R}^{d}$, if
$\hat{\psi}(u)\in\hat{\gamma}(p)$, then
$\psi(u)=\psi^{\mathcal{R}}\circ\hat{\psi}(u)\in\gamma(p)$ by definition of
$\hat{\psi}$ and $\psi^{\mathcal{R}}$. Contrapositively,
$\psi(u)\notin\gamma(p)\implies\hat{\psi}(u)\notin\hat{\gamma}(p)$. Thus, we
have

$\\{u\in\mathbb{R}^{d}\mid\psi(u)\not\in\gamma(p)\\}\subseteq\\{u\in\mathbb{R}^{d}\mid\hat{\psi}(u)\not\in\hat{\gamma}(p)\\}~{}.$

Combined with the fact that $(L,\hat{\psi})$ is calibrated with respect to
$\hat{\ell}$, we have

$\displaystyle\inf_{u\in\mathbb{R}^{d}:\psi(u)\not\in\gamma(p)}\langle
p,L(u)\rangle\geq\inf_{u\in\mathbb{R}^{d}:\hat{\psi}(u)\not\in\hat{\gamma}(p)}\langle
p,L(u)\rangle>\inf_{u\in\mathbb{R}^{d}}\langle p,L(u)\rangle~{},$

showing calibration of $\psi$. ∎

##  8 Conclusion

In this work, we introduce an embedding framework to design and analyze
consistent, convex surrogates for discrete prediction tasks. Our results are
constructive; as we outline in § 5, they can be fruitfully applied to a range
of tasks, from designing new surrogates and link functions to understanding
the consistency or inconsistency of existing surrogates. Beyond these tools,
our results shed light on fundamental questions about the design of consistent
surrogates.

Perhaps the most pressing open direction is simply to apply our framework to
prediction problems of interest. We hope that the discussion in § 5.1, and the
detailed examples in subsequent works, serve as useful guidelines for doing
so. A particularly promising domain to apply our framework is structured
prediction, where relatively few consistent surrogates are known. Indeed, our
framework has already been applied to submodular structured problems (§ 5.3)
and to max-margin losses [39].

Beyond applying our fromework, we see several interesting directions for
theoretical research. Below we outline several such directions.

#### Prediction dimension

It can be important for applications to understand the minimum prediction
dimension $d$ of a consistent convex surrogate
$L:\mathbb{R}^{d}\to\mathbb{R}^{\mathcal{Y}}_{+}$ for a given target problem,
also called its convex elicitation complexity [25]. Theorem 4 constructs a
consistent surrogate for any discrete loss, with prediction dimension
$d=n:=|\mathcal{Y}|$. In some settings, such as structured prediction and
information retrieval, a prediction dimension of $d=n$ can be prohibitively
large. For example, in § 5.3 we discuss structured problems which decompose as
$k$ simple subproblems, like pixel classification for image segmentation. The
Lovász hinge has prediction dimension $k$ for this problem, whereas our
construction would give one with $d=n=2^{k}$, an impractical number even for
relatively small images. While one could achieve $d=n-1$ with a simple
modification to our construction,666One can always reduce to $d=n-1$ in
Theorem 4 via a linear transformation from $\mathbb{R}^{n}$ to
$\mathbb{R}^{n-1}$ which is injective on $\Delta_{\mathcal{Y}}$; redefining
the surrogate appropriately, the Bayes risks will still match. it is unclear
when and how the prediction dimension could be further lowered.

Beyond studying convex elicitation complexity directly [43, 18, 25], one
promising approach to this question is to first understand the minimum $d$ for
which a polyhedral surrogate $L:\mathbb{R}^{d}\to\mathbb{R}^{\mathcal{Y}}_{+}$
embeds $\ell$, called the _embedding dimension_ of $\ell$, and then relate
this dimension to polyhedral, or general convex, elicitation complexity. One
reason this approach may be fruitful is that embeddings have much more
structure than general convex losses, such as the fact that calibrated links
arise automatically (§ 6). Yet from § 7 and similar observations, it may well
be that the lowest possible prediction dimension is achieved by an embedding.

In previous work, we introduce and present some bounds for embedding dimension
based on optimality conditions [17]. We show in particular that a target loss
has embedding dimension $1$ if and only if it hase convex elicitation
complexity $1$, underscoring the possibility that these quantities may be the
same for all discrete losses. It is unclear if these bounds are tight or if
they can be improved by leveraging information about adjacent level sets of an
embedded property. Moreover, beyond the fact that the embedding dimension
upper bounds convex elicitation complexity, it remains to understand the
relationship between these two quantities in dimensions greater than $1$.

#### Indirect elicitation as a condition for consistency

It is well-known that statistical consistency is equivalent to calibration
(Definition 4) for discrete target problems. As calibration is a much easier
condition to work with, and in particular, only involves the conditional label
distributions, the bulk of work on consistency of learning algorithms for
discrete target problems uses calibration. It is easy to verify that
calibration in turn implies indirect elicitation, meaning that exact
minimizers of the surrogate loss are linked to exact minimizers of the target.
In § 7, we show that indirect elicitation is actually _equivalent_ to
calibration, and therefore consistency, when restricting to the class of
polyhedral surrogates. As indirect elicitation is even simpler of a condition
than calibration, an important line of future work is to identify other
classes of surrogates for which this equivalence holds.

#### Polyhedral vs. smooth surrogates

The literature on convex surrogates focuses mainly on smooth surrogate losses
[11, 7, 6, 12, 58, 48, 38, 62, 5]. In practice, minimizing such surrogates
often implicitly fits a model to the full conditional label distributions. On
the other hand, Ramaswamy et al. [44, Section 1.2] contend that optimizing
nonsmooth losses may enable reduction of the prediction dimension while
maintaining consistency relative to smooth losses, improving downstream
efficiency of the learning algorithm. While generalization rates may suffer
for nonsmooth losses, polyhedral surrogates achieve linear regret transfer
bounds (§ 4.3), so the target generalization rates may remain the same; see
also Frongillo and Waggoner [24]. Even further, Lapin et al. [34] suggest that
optimizing a nonsmooth loss that directly captures the target problem of
interest, rather than a smooth one that implicitly fits to the full
conditional label distributions, can improve performance in limited data
settings. We would like to verify this intuition, with specific cases or broad
results comparing smooth and polyhedral losses.

#### Superprediction sets

An interesting direction is to understand consistent surrogates by studying
their superprediction sets, as has been done for proper losses [57]. The
superprediction set of a loss is the set of loss vectors weakly dominated by
the range of the loss: $\\{v\in\mathbb{R}^{\mathcal{Y}}\mid\exists r\;L(r)\leq
v\\}$, where the inequality holds pointwise. One appealing aspect of the
superprediction set is that it ignores the surrogate reports and focuses
directly on the set of loss vectors, in a similar fashion to the trim
operation in § 6.3. In particular, it may be that questions about the required
prediction dimension (see above) could be more readily answered by trying to
find low-dimensional structures in the superprediction set of the target loss.

#### Convex envelope

Finally, recall that we motivated the idea of an embedding as a way to
“convexify” a discrete loss. It is not clear, however, how embeddings relate
to the convex envelope operation, which is perhaps the most direct way to
perform this convexification given the map $\varphi$. For example, suppose
$L:\mathbb{R}^{d}\to\mathbb{R}^{\mathcal{Y}}_{+}$ embeds
$\ell:\mathcal{R}\to\mathbb{R}^{\mathcal{Y}}_{+}$ via the embedding
$\varphi:\mathcal{R}\to\mathbb{R}^{d}$, and consider the (polyhedral)
surrogate $L^{\prime}:\mathbb{R}^{d}\to\mathbb{R}^{\mathcal{Y}}_{+}$ given by
$L^{\prime}_{y}=(L_{y}+\mathbbm{1}_{\varphi(\mathcal{R})})^{**}$, where here
$\mathbbm{1}$ denotes the convex indicator and $(\cdot)^{**}$ the biconjugate.
(One might also consider similar operations that keep $L^{\prime}$ finite-
valued.) When is it the case that $L^{\prime}$ also embeds $\ell$? Conversely,
we would like to know when the construction in Theorem 4 can be viewed as a
convex envelope.

### Acknowledgements

We thank Arpit Agarwal and Peter Bartlett for many early discussions and
insights, Stephen Becker for a reference to Hoffman constants, and Nishant
Mehta, Enrique Nueve, and Anish Thilagar for other suggestions. This material
is based upon work supported by the National Science Foundation under Grant
Nos. CCF-1657598, IIS-2045347, and DGE-1650115.

## References

  * Abernethy et al. [2013] Jacob Abernethy, Yiling Chen, and Jennifer Wortman Vaughan.  Efficient market making via convex optimization, and a connection to online learning.  _ACM Transactions on Economics and Computation_ , 1(2):12, 2013.  URL http://dl.acm.org/citation.cfm?id=2465777.
  * Agarwal and Agarwal [2015] Arpit Agarwal and Shivani Agarwal.  On consistent surrogate risk minimization and property elicitation.  In _JMLR Workshop and Conference Proceedings_ , volume 40, pages 1–19, 2015.  URL http://www.jmlr.org/proceedings/papers/v40/Agarwal15.pdf.
  * Asif et al. [2015] Kaiser Asif, Wei Xing, Sima Behpour, and Brian D Ziebart.  Adversarial cost-sensitive classification.  In _Conference on Uncertainty in Artificial Intelligence_ , pages 92–101, 2015.
  * Aurenhammer [1987] Franz Aurenhammer.  Power diagrams: properties, algorithms and applications.  _SIAM Journal on Computing_ , 16(1):78–96, 1987\.  URL http://epubs.siam.org/doi/pdf/10.1137/0216006.
  * Bao et al. [2020] Han Bao, Clayton Scott, and Masashi Sugiyama.  Calibrated surrogate losses for adversarially robust classification.  _The Conference on Learning Theory_ , 2020.
  * Bartlett and Wegkamp [2008] Peter L Bartlett and Marten H Wegkamp.  Classification with a reject option using a hinge loss.  _Journal of Machine Learning Research_ , 9(Aug):1823–1840, 2008.
  * Bartlett et al. [2006] Peter L. Bartlett, Michael I. Jordan, and Jon D. McAuliffe.  Convexity, classification, and risk bounds.  _Journal of the American Statistical Association_ , 101(473):138–156, 2006.  URL http://amstat.tandfonline.com/doi/abs/10.1198/016214505000000907.
  * Berrada et al. [2018] Leonard Berrada, Andrew Zisserman, and M. Pawan Kumar.  Smooth loss functions for deep top-k classification.  _CoRR_ , abs/1802.07595, 2018.  URL http://arxiv.org/abs/1802.07595.
  * Boyd and Vandenberghe [2004] S.P. Boyd and L. Vandenberghe.  _Convex optimization_.  Cambridge University Press, 2004.
  * Cortes et al. [2016] Corinna Cortes, Giulia DeSalvo, and Mehryar Mohri.  Learning with rejection.  In _International Conference on Algorithmic Learning Theory_ , pages 67–82. Springer, 2016.
  * Crammer and Singer [2001] Koby Crammer and Yoram Singer.  On the algorithmic implementation of multiclass kernel-based vector machines.  _Journal of machine learning research_ , 2(Dec):265–292, 2001.
  * Duchi et al. [2018] John Duchi, Khashayar Khosravi, and Feng Ruan.  Multiclass classification, information, divergence and surrogate risk.  _The Annals of Statistics_ , 46(6B):3246–3275, 2018.
  * El-Yaniv and Wiener [2010] Ran El-Yaniv and Yair Wiener.  On the foundations of noise-free selective classification.  _Journal of Machine Learning Research_ , 11(53):1605–1641, 2010.  URL http://jmlr.org/papers/v11/el-yaniv10a.html.
  * Farnia and Tse [2016] Farzan Farnia and David Tse.  A minimax approach to supervised learning.  _Advances in Neural Information Processing Systems_ , 29, 2016.
  * Fathony et al. [2016] Rizal Fathony, Anqi Liu, Kaiser Asif, and Brian Ziebart.  Adversarial multiclass classification: A risk minimization perspective.  _Advances in Neural Information Processing Systems_ , 29, 2016.
  * Fathony et al. [2018] Rizal Fathony, Kaiser Asif, Anqi Liu, Mohammad Ali Bashiri, Wei Xing, Sima Behpour, Xinhua Zhang, and Brian D Ziebart.  Consistent robust adversarial prediction for general multiclass classification.  _arXiv preprint arXiv:1812.07526_ , 2018.
  * Finocchiaro et al. [2020] Jessie Finocchiaro, Rafael Frongillo, and Bo Waggoner.  Embedding dimension of polyhedral losses.  _The Conference on Learning Theory_ , 2020.
  * Finocchiaro et al. [2021] Jessie Finocchiaro, Rafael Frongillo, and Bo Waggoner.  Unifying lower bounds on prediction dimension of convex surrogates.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Finocchiaro et al. [2022a] Jessie Finocchiaro, Rafael Frongillo, Emma Goodwill, and Anish Thilagar.  Consistent polyhedral surrogates for top-$k$ classification and variants.  _International Conference on Machine Learning_ , 2022a.
  * Finocchiaro et al. [2022b] Jessie Finocchiaro, Rafael Frongillo, and Enrique Nueve.  The structured abstain problem and the lovász hinge.  _Conference on Learning Theory_ , 2022b.
  * Frongillo and Kash [2014] Rafael Frongillo and Ian Kash.  General truthfulness characterizations via convex analysis.  In _Web and Internet Economics_ , pages 354–370. Springer, 2014\.
  * Frongillo and Kash [2015a] Rafael Frongillo and Ian Kash.  Vector-Valued Property Elicitation.  In _Proceedings of the 28th Conference on Learning Theory_ , pages 1–18, 2015a.
  * Frongillo and Kash [2015b] Rafael Frongillo and Ian A. Kash.  On Elicitation Complexity.  In _Advances in Neural Information Processing Systems 29_ , 2015b.
  * Frongillo and Waggoner [2021] Rafael Frongillo and Bo Waggoner.  Surrogate regret bounds for polyhedral losses.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Frongillo and Kash [2021] Rafael M Frongillo and Ian A Kash.  Elicitation complexity of statistical properties.  _Biometrika_ , 108(4):857–879, 2021.
  * Gallier [2008] Jean Gallier.  Notes on convex sets, polytopes, polyhedra, combinatorial topology, voronoi diagrams and delaunay triangulations, 2008.
  * Gao and Zhou [2011] Wei Gao and Zhi-Hua Zhou.  On the consistency of multi-label learning.  In _Proceedings of the 24th annual conference on learning theory_ , pages 341–358, 2011.
  * Gneiting [2011] T. Gneiting.  Making and Evaluating Point Forecasts.  _Journal of the American Statistical Association_ , 106(494):746–762, 2011.
  * Hazan et al. [2010] Tamir Hazan, Joseph Keshet, and David A McAllester.  Direct loss minimization for structured prediction.  In _Advances in Neural Information Processing Systems_ , pages 1594–1602, 2010.
  * Hoffman [1952] Alan J Hoffman.  On approximate solutions of systems of linear inequalities.  _Journal of Research of the National Bureau of Standards_ , 49(4), 1952.
  * Lambert [2018] Nicolas S. Lambert.  Elicitation and evaluation of statistical forecasts.  _Resubmitted to _Econometrica__ , 2018.
  * Lambert et al. [2008] Nicolas S. Lambert, David M. Pennock, and Yoav Shoham.  Eliciting properties of probability distributions.  In _Proceedings of the 9th ACM Conference on Electronic Commerce_ , pages 129–138, 2008.
  * Lapin et al. [2015] Maksim Lapin, Matthias Hein, and Bernt Schiele.  Top-k multiclass svm.  In _Advances in Neural Information Processing Systems_ , pages 325–333, 2015.
  * Lapin et al. [2016] 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.
  * Lapin et al. [2018] Maksim Lapin, Matthias Hein, and Bernt Schiele.  Analysis and optimization of loss functions for multiclass, top-k, and multilabel classification.  _IEEE transactions on pattern analysis and machine intelligence_ , 40(7):1533–1554, 2018.
  * Liu [2007] Yufeng Liu.  Fisher consistency of multicategory support vector machines.  In Marina Meila and Xiaotong Shen, editors, _Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics_ , volume 2 of _Proceedings of Machine Learning Research_ , pages 291–298, San Juan, Puerto Rico, 21–24 Mar 2007. PMLR.  URL https://proceedings.mlr.press/v2/liu07b.html.
  * Madras et al. [2018] David Madras, Toni Pitassi, and Richard Zemel.  Predict responsibly: improving fairness and accuracy by learning to defer.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Menon et al. [2019] Aditya K Menon, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar.  Multilabel reductions: what is my loss optimising?  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d’ Alché-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems 32_ , pages 10600–10611. Curran Associates, Inc., 2019.  URL http://papers.nips.cc/paper/9245-multilabel-reductions-what-is-my-loss-optimising.pdf.
  * Nowak et al. [2022] Alex Nowak, Alessandro Rudi, and Francis Bach.  On the consistency of max-margin losses.  In _International Conference on Artificial Intelligence and Statistics_ , pages 4612–4633. PMLR, 2022.
  * Osband and Reichelstein [1985] Kent Osband and Stefan Reichelstein.  Information-eliciting compensation schemes.  _Journal of Public Economics_ , 27(1):107–115, June 1985.  ISSN 0047-2727.  doi: 10.1016/0047-2727(85)90031-3.  URL http://www.sciencedirect.com/science/article/pii/0047272785900313.
  * Osokin et al. [2017] Anton Osokin, Francis Bach, and Simon Lacoste-Julien.  On structured prediction theory with calibrated convex surrogate losses.  In _Advances in Neural Information Processing Systems_ , pages 302–313, 2017.
  * Ramaswamy et al. [2015] Harish Ramaswamy, Ambuj Tewari, and Shivani Agarwal.  Convex calibrated surrogates for hierarchical classification.  In _International Conference on Machine Learning_ , pages 1852–1860, 2015.
  * Ramaswamy and Agarwal [2016] Harish G Ramaswamy and Shivani Agarwal.  Convex calibration dimension for multiclass loss matrices.  _The Journal of Machine Learning Research_ , 17(1):397–441, 2016.
  * Ramaswamy et al. [2018] Harish G Ramaswamy, Ambuj Tewari, and Shivani Agarwal.  Consistent algorithms for multiclass classification with an abstain option.  _Electronic Journal of Statistics_ , 12(1):530–554, 2018.
  * Rastegari et al. [2011] Mohammad Rastegari, Chen Fang, and Lorenzo Torresani.  Scalable object-class retrieval with approximate and top-k ranking.  In _2011 International Conference on Computer Vision_ , pages 2659–2666, 2011.  doi: 10.1109/ICCV.2011.6126556.
  * Reddi et al. [2019] Sashank J Reddi, Satyen Kale, Felix Yu, Daniel Holtmann-Rice, Jiecao Chen, and Sanjiv Kumar.  Stochastic negative mining for learning with large output spaces.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , pages 1940–1949. PMLR, 2019.
  * Reid et al. [2012] Mark D Reid, Robert C Williamson, and Peng Sun.  The convexity and design of composite multiclass losses.  In _Proceedings of the 29th International Coference on International Conference on Machine Learning_ , pages 243–250, 2012.
  * Reid and Williamson [2010] M.D. Reid and R.C. Williamson.  Composite binary losses.  _The Journal of Machine Learning Research_ , 9999:2387–2422, 2010.
  * Rifkin and Klautau [2004] Ryan Rifkin and Aldebaro Klautau.  In defense of one-vs-all classification.  _The Journal of Machine Learning Research_ , 5:101–141, 2004.
  * Rockafellar [1997] R.T. Rockafellar.  _Convex analysis_ , volume 28 of _Princeton Mathematics Series_.  Princeton University Press, 1997.
  * Savage [1971] L.J. Savage.  Elicitation of personal probabilities and expectations.  _Journal of the American Statistical Association_ , pages 783–801, 1971.
  * Steinwart and Christmann [2008] Ingo Steinwart and Andreas Christmann.  _Support Vector Machines_.  Springer Science & Business Media, September 2008.  ISBN 978-0-387-77242-4.  Google-Books-ID: HUnqnrpYt4IC.
  * Steinwart et al. [2014] Ingo Steinwart, Chloé Pasin, Robert Williamson, and Siyu Zhang.  Elicitation and Identification of Properties.  In _Proceedings of The 27th Conference on Learning Theory_ , pages 482–526, 2014.
  * Tewari and Bartlett [2007] Ambuj Tewari and Peter L. Bartlett.  On the consistency of multiclass classification methods.  _The Journal of Machine Learning Research_ , 8:1007–1025, 2007.  URL http://dl.acm.org/citation.cfm?id=1390325.
  * Wang and Scott [2020] Yutong Wang and Clayton Scott.  Weston-watkins hinge loss and ordered partitions.  _Advances in neural information processing systems_ , 2020.
  * Weston and Watkins [1999] Jason Weston and Chris Watkins.  Support vector machines for multi-class pattern recognition.  In _Proceedings of the 7th European Symposium on Artificial Neural Networks_ , 1999.
  * Williamson [2014] Robert C. Williamson.  The geometry of losses.  In Maria Florina Balcan, Vitaly Feldman, and Csaba Szepesvári, editors, _Proceedings of The 27th Conference on Learning Theory_ , volume 35 of _Proceedings of Machine Learning Research_ , pages 1078–1108, Barcelona, Spain, 13–15 Jun 2014. PMLR.  URL https://proceedings.mlr.press/v35/williamson14.html.
  * Williamson et al. [2016] Robert C Williamson, Elodie Vernet, and Mark D Reid.  Composite multiclass losses.  _Journal of Machine Learning Research_ , 17(223):1–52, 2016.
  * Yang and Koyejo [2020] Forest Yang and Sanmi Koyejo.  On the consistency of top-k surrogate losses.  In _International Conference on Machine Learning_ , pages 10727–10735. PMLR, 2020.
  * Yu and Blaschko [2018] 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.
  * Zalinescu [2003] Constantin Zalinescu.  Sharp estimates for hoffman’s constant for systems of linear inequalities and equalities.  _SIAM Journal on Optimization_ , 14(2):517–533, 2003.
  * Zhang et al. [2020] Mingyuan Zhang, Harish G Ramaswamy, and Shivani Agarwal.  Convex calibrated surrogates for the multi-label f-measure.  2020\.
  * Zhang [2004] Tong Zhang.  Statistical analysis of some multi-category large margin classification methods.  _Journal of Machine Learning Research_ , 5(Oct):1225–1251, 2004.
  * Ziegler [1993] Günter M Ziegler.  Lectures on polytopes.  1993\.

##  Appendix A Power diagrams

We begin with several definitions from Aurenhammer [4].

######  Definition 11.

A _cell complex_ in $\mathbb{R}^{d}$ is a set $C$ of faces (of dimension
$0,\ldots,d$) which (i) union to $\mathbb{R}^{d}$, (ii) have pairwise disjoint
relative interiors, and (iii) any nonempty intersection of faces
$F,F^{\prime}$ in $C$ is a face of $F$ and $F^{\prime}$ and an element of $C$.

######  Definition 12.

Given sites $s_{1},\ldots,s_{k}\in\mathbb{R}^{d}$ and weights
$w_{1},\ldots,w_{k}\geq 0$, the corresponding _power diagram_ is the cell
complex given by

$\mathrm{cell}(s_{i})=\\{x\in\mathbb{R}^{d}:\forall
j\in\\{1,\ldots,k\\}\,\|x-s_{i}\|^{2}-w_{i}\leq\|x-s_{j}\|^{2}-w_{j}\\}~{}.$
(11)

######  Definition 13.

A cell complex $C$ in $\mathbb{R}^{d}$ is _affinely equivalent_ to a (convex)
polyhedron $P\subseteq\mathbb{R}^{d+1}$ if $C$ is a (linear) projection of the
faces of $P$.

Some of the convex polyhedra we study are the (negative) Bayes risks of loss
functions, whose projections onto $\Delta_{\mathcal{Y}}$ form the level sets
of the property they elicit. The following result from Aurenhammer [4]
therefore immediately applies to elicitable properties. We also make use of
the same structure for the loss itself; in particular, one can consider the
epigraph of a polyhedral convex function on $\mathbb{R}^{d}$ and the
projection down to $\mathbb{R}^{d}$. In either case, we refer to the resulting
power diagram as being _induced_ by the convex function.

######  Theorem 10 (Aurenhammer [4]).

A cell complex is affinely equivalent to a convex polyhedron if and only if it
is a power diagram.

We extend Theorem 10 to a weighted sum of convex functions, showing that the
induced power diagram is the same for any choice of strictly positive weights.

######  Lemma 5.

Let $f_{1},\ldots,f_{m}:\mathbb{R}^{d}\to\mathbb{R}$ be polyhedral convex
functions. The power diagram induced by $\sum_{i=1}^{m}p_{i}f_{i}$ is the same
for all $p\in\mathrm{inter}(\Delta_{\mathcal{Y}})$.

###### Proof.

For any polyhedral convex function $g$ with epigraph $P$, the proof of
Aurenhammer [4, Theorem 4] shows that the power diagram induced by $g$ is
determined by the facets of $P$. Let $F$ be a facet of $P$, and $F^{\prime}$
its projection down to $\mathbb{R}^{d}$. It follows that $g|_{F^{\prime}}$ is
affine, and thus $g$ is differentiable on $\mathrm{inter}(F^{\prime})$ with
constant derivative $d\in\mathbb{R}^{d}$. Conversely, for any subgradient
$d^{\prime}$ of $g$, the set of points
$\\{x\in\mathbb{R}^{d}:d^{\prime}\in\partial g(x)\\}$ is the projection of a
face of $P$; we conclude that $F=\\{(x,g(x))\in\mathbb{R}^{d+1}:d\in\partial
g(x)\\}$ and $F^{\prime}=\\{x\in\mathbb{R}^{d}:d\in\partial g(x)\\}$.

Now let $f:=\sum_{i=1}^{k}f_{i}$ with epigraph $P$, and
$f^{\prime}:=\sum_{i=1}^{k}p_{i}f_{i}$ with epigraph $P^{\prime}$. By
Rockafellar [50], $f,f^{\prime}$ are polyhedral. We now show that $f$ is
differentiable whenever $f^{\prime}$ is differentiable:

$\displaystyle\partial f(x)=\\{d\\}$ $\displaystyle\iff\sum_{i=1}^{k}\partial
f_{i}(x)=\\{d\\}$ $\displaystyle\iff\forall i\in\\{1,\ldots,k\\},\;\partial
f_{i}(x)=\\{d_{i}\\}$ $\displaystyle\iff\forall
i\in\\{1,\ldots,k\\},\;\partial p_{i}f_{i}(x)=\\{p_{i}d_{i}\\}$
$\displaystyle\iff\sum_{i=1}^{k}\partial
p_{i}f_{i}(x)=\left\\{\sum_{i=1}^{k}p_{i}d_{i}\right\\}$
$\displaystyle\iff\partial
f^{\prime}(x)=\left\\{\sum_{i=1}^{k}p_{i}d_{i}\right\\}~{}.$

From the above observations, every facet of $P$ is determined by the
derivative of $f$ at any point in the interior of its projection, and vice
versa. Letting $x$ be such a point in the interior, we now see that the facet
of $P^{\prime}$ containing $(x,f^{\prime}(x))$ has the same projection, namely
$\\{x^{\prime}\in\mathbb{R}^{d}:\nabla f(x)\in\partial
f(x^{\prime})\\}=\\{x^{\prime}\in\mathbb{R}^{d}:\nabla
f^{\prime}(x)\in\partial f^{\prime}(x^{\prime})\\}$. Thus, the power diagrams
induced by $f$ and $f^{\prime}$ are the same. The conclusion follows from the
observation that the above held for any strictly positive weights $p$, and $f$
was fixed. ∎

We now include the full proof of Lemma 2.

See 2

###### Proof.

First, observe that $L:\mathbb{R}^{d}\to\mathbb{R}^{\mathcal{Y}}_{+}$ is
finite and bounded from below (by $0$), and thus its infimum is finite.
Therefore, we can apply Rockafellar [50, Corollary 19.3.1] to conclude that
its infimum is attained for all $p\in\Delta_{\mathcal{Y}}$ and is therefore
minimizable. Thus, $L$ elicits a property.

For all $p$, let $P(p)$ be the epigraph of the convex function
$u\mapsto\langle p,L(u)\rangle$. From Lemma 5, we have that the power diagram