On the Consistency of Max-Margin Losses

Alex Nowak-Vila Alessandro Rudi Francis Bach

ENS-INRIA-PSL Paris, France ENS-INRIA-PSL Paris, France ENS-INRIA-PSL Paris,
France

###### Abstract

The foundational concept of Max-Margin in machine learning is ill-posed for
output spaces with more than two labels such as in structured prediction. In
this paper, we show that the Max-Margin loss can only be consistent to the
classification task under highly restrictive assumptions on the discrete loss
measuring the error between outputs. These conditions are satisfied by
distances defined in tree graphs, for which we prove consistency, thus being
the first losses shown to be consistent for Max-Margin beyond the binary
setting. We finally address these limitations by correcting the concept of
Max-Margin and introducing the Restricted-Max-Margin, where the maximization
of the loss-augmented scores is maintained, but performed over a subset of the
original domain. The resulting loss is also a generalization of the binary
support vector machine and it is consistent under milder conditions on the
discrete loss.

##  1 INTRODUCTION

One of the first binary classification methods learned in a machine learning
course is the support vector machine (SVM) (Boser et al., 1992; Cortes and
Vapnik, 1995) and it is introduced using the principle of maximum margin:
assuming the data are linearly separable, the classification hyperplane must
maximize the separation to the observed examples. Having this intuition in
mind, the same principle has been used to extend this notion to larger output
spaces $\mathcal{Y}$, such as multi-class classification (Crammer and Singer,
2001) and structured prediction (Taskar et al., 2004; Tsochantaridis et al.,
2005), where the separation to the observed examples is controlled by a
discrete loss $L(y,y^{\prime})$ measuring the error between outputs $y$ and
$y^{\prime}$. The resulting method generalizes the binary SVM and corresponds
to minimizing the so-called Max-Margin loss

$S_{\operatorname{M}}(v,y)=\max_{y^{\prime}\in\mathcal{Y}}~{}L(y,y^{\prime})+v_{y^{\prime}}-v_{y},$
(1)

where $v\in\mathbb{R}^{|\mathcal{Y}|}$ is a vector with coordinate $v_{y}$
encoding the score for output $y$. Unfortunately, this method may not be
_consistent_ , i.e., minimizing the Max-Margin loss (1) may not lead to a
minimization of the discrete loss $L$ of interest. In particular, it is known
that the Max-Margin loss is only consistent for the 0-1 loss under the
dominant label condition, i.e., when for every input there exists an output
element with probability larger than $1/2$ (Liu, 2007), which is always
satisfied in the binary case. However, far less is known for other tasks.
Indeed, the Max-Margin loss is widely used for structured output spaces where
the discrete loss $L$ defining the task is different than the 0-1 loss, under
the name of Structural SVM (SSVM) (Taskar et al., 2005; Caetano et al., 2009;
Smith, 2011) or Max-Margin Markov Networks ($\operatorname{M^{3}N}$) (Taskar
et al., 2005). In this general setting, the following questions remain
unanswered:

  * (i)

_Does there exist a necessary condition on $L$ for consistency to hold? Does
it exist a space of losses for which consistency holds? Can we generalize the
consistency result under the dominant label assumption beyond the 0-1 loss?_

  * (ii)

_Can we correct the Max-Margin loss to make it consistent by maintaining the
additive and maximization structure of the Max-Margin loss?_

We answer these questions in this paper. In particular, we make the following
contributions:

  * -

We prove that the Max-Margin loss can only be consistent under a restrictive
necessary condition on the structure of the loss $L$, indeed, the loss $L$ has
to be a distance and satisfy the triangle inequality as an _equality_ for
several groups of outputs. As a positive result, we show that a distance
defined in a tree graph, such as the absolute deviation loss used in ordinal
regression, satisfies this condition and it is consistent, thus providing the
first set of losses for which consistency holds beyond the binary setting. We
also extend the existing _partial_ consistency result of the 0-1 loss by
extending the result under the dominant label condition to all losses that are
distances.

  * -

As a secondary contribution, we introduce the Restricted-Max-Margin loss,
where the maximization of the loss-augmented scores defining the Max-Margin
loss is restricted to a subset of the simplex. The resulting loss also
generalizes the binary SVM and it is consistent under milder assumptions on
$L$. Moreover, we show the connections between these losses and the Max-Min-
Margin loss (Fathony et al., 2016; Duchi et al., 2018; Nowak-Vila et al.,
2020), where consistency always holds independently of the discrete loss $L$.

##  2 MAX-MARGIN AND MAIN RESULTS

In this section we introduce the concept of Max-Margin learning and its
consistency from its origins in binary classification to the structured output
setting. This is followed by the presentation of the main results of this
paper and its implications are discussed.

###  2.1 Max-Margin Learning

##### Binary output.

Let $(x_{1},y_{1}),\ldots,(x_{n},y_{n})$ be $n$ examples of input-output pairs
sampled from an unknown distribution $\rho$ defined in
$\mathcal{X}\times\mathcal{Y}$. Let us first assume that the input space
$\mathcal{X}$ is a vector space and $\mathcal{Y}=\\{-1,1\\}$ represents binary
labels. The goal is to construct a binary-valued function
$f:\mathcal{X}\xrightarrow[]{}\mathcal{Y}$ minimizing the expected
classification error

$\mathcal{E}(f)=\operatorname{\mathbb{E}}_{(x,y)\sim\rho}L(f(x),y),$ (2)

where $L(y,y^{\prime})=1(y\neq y^{\prime})$ is the binary 0-1 loss. The
concept of max-margin was initially defined in this setting to construct a
predictor of the form $\operatorname{sign}(g(x))$ where $g(x)=w^{\top}x+b$ is
an affine function defining a hyperplane with maximum separation to the
examples assuming linearly separable data (Boser et al., 1992). In this
setting, an example $x_{i}$ is correctly classified if
$(w^{\top}x_{i}+b_{i})y_{i}>0$ and misclassified otherwise. The max-margin
hyperplane can be found by minimizing $\|w\|_{2}^{2}$ under the constraint
$(w^{\top}x_{i}+b)y_{i}\geq 1$ for all $n$ examples. When the data are not
linearly separable, some examples are allowed to be misclassified by
introducing some non-negative _slack variables_ $\xi_{i}$ and solving the
optimization problem known as the support vector machine (SVM) (Cortes and
Vapnik, 1995):

$\left\\{\begin{array}[]{ll}\underset{w,b,\xi}{\min}&\frac{1}{n}\sum_{i=1}^{n}\xi_{i}+\frac{\lambda}{2}\|w\|_{2}^{2}\\\
\text{s.t.}&(w^{\top}x_{i}+b)y_{i}\geq 1-\xi_{i},\hskip 11.38092pt\xi_{i}\geq
0,~{}\forall i\in[n],\end{array}\right.$

where $\lambda>0$ is a parameter used to balance the first term with the
second. We can re-write the constraints as $\xi_{i}\geq 1-y_{i}g(x_{i})$ for
non-negative $\xi_{i}$’s and extend the affine hypothesis space to a generic
functional space $\mathcal{G}$ with associated norm $\|\cdot\|_{\mathcal{G}}$
to allow for non-linear predictors, such as reproducing kernel Hilbert spaces
(RKHS) (Aronszajn, 1950). Then, the problem above can be written as a convex
regularized empirical risk minimization (ERM) (Vapnik, 1992) problem

$\min_{g\in\mathcal{G}}~{}\frac{1}{n}\sum_{i=1}^{n}S_{\operatorname{M}}(g(x_{i}),y_{i})+\frac{\lambda}{2}\|g\|_{\mathcal{G}}^{2},$
(3)

where $S_{\operatorname{M}}(v,y)=\max(1-yv,0)$ is the binary Max-Margin loss
(also called SVM loss), and now $\lambda$ can be interpreted as the
regularization parameter. An important property of the classification method
is that the estimated predictor solving (3) over all measurable functions
converges to the predictor $f^{\star}$ minimizing the expected classification
error (2) in the infinite data regime ($n\to\infty$ and $\lambda\to 0$)
(Vapnik, 2013). More concretely, the minimizer $g^{\star}$ of the expected
risk $\operatorname{\mathbb{E}}_{(x,y)\sim\rho}S_{\operatorname{M}}(g(x),y)$
must satisfy $f^{\star}=\operatorname{sign}(g^{\star})$. This property is
called Fisher consistency (Bartlett et al., 2006) (or simply consistency) and
can be studied in terms of the conditional expectation $q(x):=\rho(1|x)$, as
$f^{\star}(x)$ and $g^{\star}(x)$ can be characterized in terms of this
quantity 111This is because $f^{\star}$ and $g^{\star}$ are minimizers over
all measurable functions of an expectation over $\mathcal{X}$.. Note that in
the rest of the paper we will drop the dependence in $x$ from the function
$q$: a statement $P(q)$ for all $q\in[0,1]$ must then be read as $P(q(x))$ for
all $x\in\mathcal{X}$. Let
$v_{\operatorname{M}}^{\star}(q)\subseteq\mathbb{R}$ and
$y^{\star}(q)\subseteq\mathcal{Y}$ be the minimizers of the conditional risks
$\operatorname{\mathbb{E}}_{y^{\prime}\sim
q}S_{\operatorname{M}}(v,y^{\prime})$ and
$\operatorname{\mathbb{E}}_{y^{\prime}\sim q}L(y,y^{\prime})$, respectively.
Then, Fisher consistency is equivalent to say that if $v\in
v_{\operatorname{M}}^{\star}(q)$, then $\operatorname{sign}(v)\in
y^{\star}(q)$ for all $q\in[0,1]$ (Devroye et al., 2013).

Figure 1:  Left: Plots of the conditional risks of the Max-Margin loss for
$q=0.4,q=0.6$ and $q=0$, respectively. The conditional risk in the set of
minimizers $v_{\operatorname{M}}^{\star}(q)$ is plotted with a thick point /
line. Middle: Plot of $S_{\operatorname{M}}(v,1),S_{\operatorname{MM}}(v,1)$
and $S_{\operatorname{RM}}(v,1)$ in the binary setting with $v=v_{1}=-v_{-1}$.
In this case, $S_{\operatorname{M}}=2S_{\operatorname{RM}}$ (so both losses
generalize the binary SVM up to a factor of 2) and $S_{\operatorname{M}}$ is
the only one upper-bounding the 0-1 loss. Moreover, the three losses are
consistent with the 0-1 loss. Right: Distance defined in a tree: the
distance/loss between two nodes is the sum of the distances between adjacent
nodes of the path between them. For every triplet of outputs
$y,y^{\prime},y^{\prime\prime}\in\mathcal{Y}$, either they are aligned in a
path, or there exists $z\in\mathcal{Y}$ belonging to the shortest path between
all pairs.

This property is satisfied as (see also left Fig. 1):

$\displaystyle y^{\star}(q)$
$\displaystyle=\left\\{\begin{array}[]{lr}\\{1\\}&q\in(1/2,1]\\\
\\{-1,1\\}&q=1/2\\\ \\{-1\\}&q\in[0,1/2),\end{array}\right.,$ $\displaystyle
v_{\operatorname{M}}^{\star}(q)$
$\displaystyle=\left\\{\begin{array}[]{lr}~{}[1,\infty)&q=1\\\
~{}\\{1\\}&q\in(1/2,1)\\\ ~{}[-1,1]&q=1/2\\\ ~{}\\{-1\\}&q\in(0,1/2)\\\
~{}(-\infty,-1]&q=0.\\\ \end{array}\right..$

##### Structured prediction.

In the structured prediction setting, we have $k=|\mathcal{Y}|$ possible
outputs and the goal is to estimate a discrete-valued function $f$ minimizing
(2) where now $L:\mathcal{Y}\times\mathcal{Y}\xrightarrow[]{}\mathbb{R}$ is a
generic non-negative discrete loss function between output pairs defining the
task at hand. We construct predictors of the form
$\operatorname*{arg\;max}_{y\in\mathcal{Y}}~{}g_{y}(x)$, where
$g:\mathcal{X}\xrightarrow[]{}\mathbb{R}^{k}$ is a vector-valued function
assigning scores to each of the $k$ possible outputs. The maximum margin
principle from binary classification is generalized as follows. For every
example $(x_{i},y_{i})$, the method minimizes the squared norm
$\|g\|_{\mathcal{G}}^{2}$ under the constraints

$g_{y_{i}}(x_{i})\geq\underbrace{L(y,y_{i})+g_{y}(x_{i})}_{\text{loss-
augmented scores}},$ (4)

for all possible outputs $y$. By writing the above constraint as
$g_{y_{i}}(x_{i})-g_{y}(x_{i})\geq L(y,y_{i})$, we observe that this
generalizes the condition $y_{i}g(x_{i})\geq 1$ from binary classification
when $g=g_{1}=-g_{-1}$ so that the argmax corresponds to the sign and $L$ is
the binary 0-1 loss. As in the binary case, introducing slack variables and
turning it into a regularized ERM problem of the form (3) we obtain the Max-
Margin loss
$S_{\operatorname{M}}(v,y)=\max_{y^{\prime}\in\mathcal{Y}}~{}L(y,y^{\prime})+v_{y^{\prime}}-v_{y}$,
which is constructed as a maximization of the loss-augmented scores defined in
(4). To ease notation, the dependence of $S$ on the loss $L$ is deduced from
the context. The Max-Margin loss (1) is known as the Crammer-Singer SVM
(Crammer and Singer, 2001) when $L$ is the 0-1 loss, and it is also widely
used in structured prediction settings with exponentially large output spaces
under the name of Structural SVM (Joachims, 2006) or Max-Margin Markov
Networks ($\operatorname{M^{3}N}$) (Taskar et al., 2004) by using losses
between structured outputs such as sequences, permutations, graphs, etc (BakIr
et al., 2007). An interesting property of this loss is that it upper-bounds
the discrete loss as
$L(\operatorname*{arg\;max}_{y^{\prime}\in\mathcal{Y}}~{}v_{y^{\prime}},y)\leq
S_{\operatorname{M}}(v,y)$, for all $v\in\mathbb{R}^{k}$ and
$y\in\mathcal{Y}$, which can guide us to think that minimizing
$\operatorname{\mathbb{E}}_{(x,y)\sim\rho}S_{\operatorname{M}}(g(x),y)$ leads
to minimizing
$\operatorname{\mathbb{E}}_{(x,y)\sim\rho}L(\operatorname*{arg\;max}_{y^{\prime}\in\mathcal{Y}}~{}g_{y^{\prime}}(x),y)$.
Unfortunately this intuition is misleading, as this bound is in general far
from tight. Analogously to the binary case, let $q:\mathcal{X}\to\Delta$ be
the conditional distribution where $\Delta$ is the simplex over $\mathcal{Y}$
(we again drop the dependence on $x$, since each statement must be read as
holding for every $x\in\mathcal{X}$). Moreover, we define for every $q$ the
set of minimizers of the conditional risks as

$\displaystyle y^{\star}(q)$
$\displaystyle=\operatorname*{arg\;min}_{y\in\mathcal{Y}}~{}L_{y}^{\top}q\subseteq\mathcal{Y},$
$\displaystyle v_{\operatorname{M}}^{\star}(q)$
$\displaystyle=\operatorname*{arg\;min}_{v\in\mathbb{R}^{k}}~{}S_{\operatorname{M}}(v)^{\top}q\subseteq\mathbb{R}^{k},$

where $L_{y}=(L(y,y^{\prime}))_{y^{\prime}\in\mathcal{Y}}\in\mathbb{R}^{k}$ is
the $y$-th row of the loss matrix and
$S_{\operatorname{M}}(v)=(S_{\operatorname{M}}(v,y^{\prime}))_{y^{\prime}\in\mathcal{Y}}\in\mathbb{R}^{k}$.
We say that $S_{\operatorname{M}}$ is Fisher consistent to $L$ if for all
$q\in\Delta$

$v\in
v_{\operatorname{M}}^{\star}(q)\implies\underset{y\in\mathcal{Y}}{\operatorname*{arg\;max}}~{}v_{y}\in
y^{\star}(q).$ (5)

Related works on consistency of Max-Margin.  The Max-Margin loss is only
consistent to the 0-1 loss under the dominant label assumption
$\max_{y\in\mathcal{Y}}q_{y}\geq 1/2$ (Liu, 2007). Ramaswamy et al. (2018)
show that it is consistent to the “abstain” loss, but in this case the loss
appearing in the definition (1) is not the same as the classification loss
$L$. McAllester (2007) studies consistency of non-convex versions of max-
margin methods on linear hypothesis spaces. There exist several
generalizations of the binary SVM to larger output spaces other than Max-
Margin (Dogan et al., 2016) such as Weston-Watkins (WW-SVM) (Weston and
Watkins, 1999), Lee-Lin-Wahba (LLW-SVM) (Lee et al., 2004), Simplex-Coding
(SC-SVM) (Mroueh et al., 2012), with the last two being consistent and defined
as sums. However, the only loss with a max-structure is (1), which makes it
computationally feasible to work in structured spaces of exponential size such
as sequences or permutations. The Max-Min-Margin loss (Fathony et al., 2016;
Duchi et al., 2018; Nowak-Vila et al., 2020) (defined below in Eq. 8) is
always consistent, it has a max-min structure and can be used in structured
prediction settings. However, it does not correspond to the SVM in the binary
setting, so it cannot be considered a generalization of the binary SVM.

###  2.2 Main Results

We assume that $L$ is symmetric and that $L(y,y^{\prime})=0$ if and only if
$y=y^{\prime}$. Symmetry of $L$ is assumed for the sake of exposition, but it
is only required for the results on Max-Margin.

##### Main Results on Max-Margin.

The following Thm. 2.1 is our main negative result.

######  Theorem 2.1 (Necessary condition for consistency
$S_{\operatorname{M}}$).

Let $k=|\mathcal{Y}|>2$. If the Max-Margin loss is consistent to $L$, then $L$
is a distance and for every three outputs $y_{1},y_{2},y_{3}\in\mathcal{Y}$,
there exists $z\in\mathcal{Y}$ for which the following three identities hold:

$\displaystyle L(y_{1},y_{2})$ $\displaystyle=L(y_{1},z)+L(z,y_{2}),$
$\displaystyle L(y_{1},y_{3})$ $\displaystyle=L(y_{1},z)+L(z,y_{3}),$
$\displaystyle L(y_{2},y_{3})$ $\displaystyle=L(y_{2},z)+L(z,y_{3}).$

If $z=y_{2}$ in Thm. 2.1, then the only informative condition is
$L(y_{1},y_{3})=L(y_{1},y_{2})+L(y_{2},y_{3})$ as $L$ is assumed to be
symmetric, which means that the outputs $y_{1},y_{2},y_{3}$ are ‘aligned’ in
the output space (analogously for $z=y_{2},y_{3}$). On the other hand, if
$z\neq y_{1},y_{2},y_{3}$, then the three equations are informative and all
distances between the pairs can be decomposed into distances to $z$. The
following discrete losses do not satisfy the above necessary condition (see
Section 2 of Appendix):

  * -

Losses which are not distances (such as the squared discrete loss
$(y-y^{\prime})^{2}$).

  * -

Losses with full rank loss matrix with existing
$q\in\operatorname{int}(\Delta)$ for which all outputs are optimal, i.e.,
$y^{\star}(q)=\mathcal{Y}$ (such as the 0-1 loss).

  * -

Hamming losses
$L(y,y^{\prime})=\frac{1}{M}\sum_{m=1}^{M}L_{m}(y_{m},y_{m}^{\prime})$ with
$y,y^{\prime}\in\Pi_{m=1}^{M}\mathcal{Y}_{m}$ where $L_{m}$ does not satisfy
the necessary conditions for some $m=1,\ldots,M$.

  * -

Hamming loss on permutations
$L(\sigma,\sigma^{\prime})=\frac{1}{M}\sum_{m=1}^{M}1(\sigma(m)\neq\sigma^{\prime}(m))$
with $\sigma,\sigma^{\prime}$ permutations of size $M$, used for graph
matching (Petterson et al., 2009; Caetano et al., 2009).

It is an open question whether the necessary condition of Thm. 2.1 is also
sufficient. The following Thm. 2.2 shows that distances defined in a tree,
which always satisfy this condition (see right Fig. 1), are indeed consistent.

######  Theorem 2.2 (Sufficient condition for consistency
$S_{\operatorname{M}}$).

If $L$ is a distance defined in a tree, then the Max-Margin loss is consistent
to $L$.

An important example of these losses is the _absolute deviation_ loss used in
ordinal regression,

$L(y,y^{\prime})=|\gamma_{y}-\gamma_{y^{\prime}}|,\hskip
14.22636pt\gamma\in\mathbb{R}^{k},$

Figure 2: From left to right: plots of
$S_{\operatorname{M}}(v,1),S_{\operatorname{MM}}(v,1)$ and
$S_{\operatorname{RM}}(v,1)$ in the three-label setting with $v^{\top}1=0$ for
the 0-1 loss (note that $S(v+c1,y)=S(v,y)$ for all three losses). The Max-Min-
Margin and the Restrictive-Max-Margin loss coincide in the bottom-left region,
but the Max-Min-Margin loss has three extra activated faces in the top-right
region of the plot which are in general unnecessary for consistency, while the
Restricted-Max-Margin uses just the necessary ones. The Max-Margin in the left
plot uses just three faces, being insufficient for consistency.

for which the associated tree is a chain. Note that these losses are not the
only ones satisfying the necessary condition given by Thm. 2.1. Indeed, the
Hamming loss with $M=2$, $\mathcal{Y}_{1}=\mathcal{Y}_{2}=\\{-1,1\\}$ and
$L_{1},L_{2}$ the 0-1 loss is _not_ a distance in a tree, satisfies the
necessary condition, and consistency can be proven to hold (see Section 2 of
Appendix). The following Prop. 2.3 gives a much milder sufficient condition to
ensure _partial_ consistency under the dominant label assumption, thus
generalizing the well-known results from Liu (2007).

######  Proposition 2.3 (Sufficient condition for _partial_ consistency
$S_{\operatorname{M}}$).

If $L$ is a distance, then the Max-Margin loss is consistent to $L$ under the
dominant label assumption, i.e., $\max_{y\in\mathcal{Y}}~{}q_{y}\geq 1/2$.

In other words, if the learning task is defined by a distance and it is close
to deterministic, then the Max-Margin loss is consistent to the task.

##### Beyond Max-Margin.

To overcome the limitations imposed by the maximum margin, but retaining the
maximization structure of the loss, we propose a novel generalization of the
binary SVM to structured prediction by restricting the maximization of the
loss-augmented scores in (1). First, note that the Max-Margin loss can be
written as a maximization over the simplex
${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\Delta}$
over $\mathcal{Y}$ as

$S_{\operatorname{M}}(v,y)=\max_{q\in{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\Delta}}~{}L_{y}^{\top}q+v^{\top}q-v_{y}.$
(6)

We restrict the maximization to the so-called _prediction set_
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\Delta(y)}=\\{q\in\Delta~{}|~{}y\in
y^{\star}(q)\\}$, defined as the set of probabilities for which $y$ is
optimal. In binary classification the sets are $\Delta(-1)=[0,1/2]$ and
$\Delta(1)=[1/2,1]$. The resulting _Restricted-Max-Margin_ loss reads

$S_{\operatorname{RM}}(v,y)=\max_{q\in{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\Delta(y)}}~{}L_{y}^{\top}q+v^{\top}q-v_{y}.$
(7)

This loss satisfies $2S_{\operatorname{RM}}=S_{\operatorname{M}}$ in the
binary setting (see middle Fig. 1), thus, it corresponds to the binary SVM up
to a scaling with a factor of two. The following Thm. 2.4 states that
consistency of $S_{\operatorname{M}}$ implies consistency of
$S_{\operatorname{RM}}$ and provides a sufficient condition for consistency of
$S_{\operatorname{RM}}$.

######  Theorem 2.4 (Sufficient condition for consistency
$S_{\operatorname{RM}}$).

The Restricted-Max-Margin loss is consistent to $L$ whenever the Max-Margin is
consistent. Moreover, if $L$ satisfies $q_{y}>0$ for every $y$ optimal for
$q\in\Delta$, i.e., $q\in\Delta(y)$, then the Restricted-Max-Margin is also
consistent to $L$.

In other words, if the output $y$ is optimal for $q$, then the probability of
this label has to be strictly greater than zero $q_{y}>0$. The 0-1 loss, which
does not satisfy the necessary condition of Thm. 2.1, satisfies the sufficient
condition for the Restricted-Max-Margin, as $\min_{q\in\Delta(y)}q_{y}=1/k$
for all $y\in\mathcal{Y}$. However, there are still losses for which (7) is
not consistent to, such as the squared discrete loss $(z-y)^{2}$ (see right of
Fig. 3). The remaining inconsistencies can be resolved by going beyond the
maximization structure into a max-min structure. The resulting loss is the so-
called _Max-Min-Margin loss_ (Fathony et al., 2016; Duchi et al., 2018; Nowak-
Vila et al., 2020) defined as

$S_{\operatorname{MM}}(v,y)=\max_{q\in\Delta}\boldsymbol{{\color[rgb]{0,0.88,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.88,0}\pgfsys@color@cmyk@stroke{0.91}{0}{0.88}{0.12}\pgfsys@color@cmyk@fill{0.91}{0}{0.88}{0.12}\min_{z\in\mathcal{Y}}}}~{}L_{\boldsymbol{\color[rgb]{0,0.88,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.88,0}\pgfsys@color@cmyk@stroke{0.91}{0}{0.88}{0.12}\pgfsys@color<EMAIL_ADDRESS>(8)

It is known (Nowak-Vila et al., 2020) that the loss (8) is _always_ consistent
to $L$. As shown in Fig. 1 (middle), this loss does not correspond to the SVM
in the binary setting because it has two symmetric kinks instead of one. See
also Fig. 2 to compare the shape of the different losses for $k=3$. Hence,
while the structure of the loss gets more computationally involved from the
Max-Margin loss (6) to the Max-Min-Margin loss (8), passing by the Restricted-
Max-Margin loss (7), the consistency properties of these losses improve from
one to the next.

##  3 BACKGROUND AND PRELIMINARY RESULTS

###  3.1 Background on Polyhedral Losses

##### Fisher consistency.

Let us now consider a generic loss
$S:\mathbb{R}^{k}\times\mathcal{Y}\rightarrow\mathbb{R}$ and let’s generalize
the argmax computing the prediction from the scores in the previous section to
a generic _decoding_ function $d:\mathbb{R}^{k}\rightarrow\mathcal{Y}$. The
set of minimizers $v^{\star}(q)\subseteq\mathbb{R}^{k}$ of the conditional
risk $S(v)^{\top}q$ is also defined as before. We say that $S$ is _Fisher
consistent_ to $L$ (Tewari and Bartlett, 2007) under the decoding
$d:\mathbb{R}^{k}\rightarrow\mathcal{Y}$ if

$v\in v^{\star}(q)\implies d(v)\in y^{\star}(q),$ (9)

for all $q\in\Delta$. If the decoding is not specified, it means that there
exists a decoding satisfying this property. An important quantity throughout
the paper is the _Bayes risk_ , a _concave_ function defined as the minimum of
the conditional expected loss respectively for $L$ and $S$:

$H_{L}(q)=\min_{y\in\mathcal{Y}}~{}L_{y}^{\top}q,\hskip
22.76228ptH_{S}(q)=\min_{v\in\mathbb{R}^{k}}~{}S(v)^{\top}q.$

##### Embedding of discrete losses.

Fisher consistency in Eq. 9 states that every minimizer $v\in v^{\star}(q)$
can be assigned to a solution of the discrete task using the decoding $d$. For
the analysis of this paper, it will be useful to work using the concept of
embeddability between losses (Finocchiaro et al., 2019), a stronger notion
than Fisher consistency.

######  Definition 3.1 (Embeddability).

$S$ _embeds_ $L$ if there exists an embedding
$\psi:\mathcal{Y}\rightarrow\mathbb{R}^{k}$ such that: (i) $y\in
y^{\star}(q)\iff\psi(y)\in v^{\star}(q),~{}\forall q\in\Delta$, and (ii)
$S(\psi(y))=L_{y},~{}\forall y\in\mathcal{Y}$.

Condition (i) states that every solution of the discrete problem corresponds
to a solution of the problem in $S$ and vice versa. In particular, this rules
out many smooth plug-in classifiers such as the squared loss or logistic
regression, because they predict the vector of probabilities $q$ which cannot
be recovered from the discrete predictor $y^{\star}(q)$. It is known
(Finocchiaro et al., 2019) that the existence of an embedding $\psi$
satisfying (i) implies the existence of a decoding $d$ satisfying Eq. 9, so it
is already a sufficient condition for Fisher consistency. Note that both Eq.
(9) and condition (i) are assumptions on the predictors $y^{\star}$ and
$v^{\star}$, but there exist several losses $L$ with the same set of
minimizers $y^{\star}(q)$ of the conditional risk $L_{y}^{\top}q$. The same
can be said for the objects $v^{\star}$ and $S$. Condition (ii) restricts the
relationship between pairs of losses by assuming that $L$ can be recovered
from $S$ using the embedding $\psi$. The following Prop. 3.2 shows that $S$
embedding $L$ is equivalent to having the same Bayes risks.

######  Proposition 3.2 (Finocchiaro et al. (2019)).

$S$ embeds $L$ if and only if $H_{L}=H_{S}$.

Moreover, it is known that any discrete loss $L$ is embedded by at least one
loss $S$ (Theorem 2 in Finocchiaro et al. (2019)), which corresponds precisely
to the Max-Min-Margin loss $S_{\operatorname{MM}}$ defined in Eq. 8. Indeed,
$S_{\operatorname{MM}}$ and $L$ have the same Bayes risk as

$\displaystyle H_{\operatorname{MM}}(q)$
$\displaystyle=\min_{v\in\mathbb{R}^{k}}\big{(}\max_{p\in\Delta}\min_{y\in\mathcal{Y}}~{}L_{y}^{\top}p+v^{\top}p\big{)}-v^{\top}q$
$\displaystyle=\min_{v\in\mathbb{R}^{k}}(-H_{L})^{*}(v)-v^{\top}q=H_{L}(q),$

where $h^{*}(u)=\sup_{s\in\mathbb{R}^{k}}~{}u^{\top}s-h(s)$ is the Fenchel
conjugate of $h$. It can be checked (Nowak-Vila et al., 2020) that the
embedding is $\psi(y)=-L_{y}$ and it is always Fisher consistent to $L$ under
the argmax decoding.

###  3.2 Preliminary Results

##### Relationship between losses and Bayes risks.

What makes the Max-Min-Margin loss simple to analyze is its Fenchel-Young
structure (Blondel et al., 2020), i.e., it can be written in the form
$S(v,y)=\Omega^{*}(v)-v_{y}$, for a certain convex function $\Omega$ defined
in the simplex. We extend this notion by allowing the convex function $\Omega$
to depend on the label $y$ as

$S(v,y)=(\Omega^{y})^{*}(v)-v_{y}.$ (10)

The losses $S_{\operatorname{M}},S_{\operatorname{RM}}$ and
$S_{\operatorname{MM}}$ can be written in this form with

$\displaystyle\Omega_{\operatorname{MM}}^{y}(q)$
$\displaystyle=-\min_{y^{\prime}\in\mathcal{Y}}L_{y^{\prime}}^{\top}q+i_{\Delta}(q),$
$\displaystyle\Omega_{\operatorname{M}}^{y}(q)$
$\displaystyle=-L_{y}^{\top}q+i_{\Delta}(q),$
$\displaystyle\Omega_{\operatorname{RM}}^{y}(q)$
$\displaystyle=-L_{y}^{\top}q+i_{\Delta(y)}(q),$

where $i_{U}(u)=0$ if $u\in U$ and $\infty$ otherwise. The first equation is
the only one independent of $y$ and we remove its dependence by simply writing
$\Omega_{\operatorname{MM}}$. The following Prop. 3.3 relates the functions
$\Omega_{\operatorname{MM}},\Omega_{\operatorname{M}}^{y}$ and
$\Omega_{\operatorname{RM}}^{y}$.

######  Proposition 3.3.

The following holds:
$\Omega_{\operatorname{MM}}=\max_{y\in\mathcal{Y}}~{}\Omega_{\operatorname{M}}^{y}$
and
$(\Omega_{\operatorname{MM}})^{*}=\max_{y\in\mathcal{Y}}~{}(\Omega_{\operatorname{RM}}^{y})^{*}$.

###### Proof.

The first identity is trivial from the definition. For the second identity,
note that by construction the prediction sets necessarily cover the simplex as
$\Delta=\cup_{y^{\prime}\in\mathcal{Y}}~{}\Delta(y^{\prime})$. Hence,

$\displaystyle(\Omega_{\operatorname{MM}})^{*}(v)$
$\displaystyle=\max_{y\in\mathcal{Y}}\big{(}\max_{q\in\Delta(y)}\min_{y^{\prime}\in\mathcal{Y}}~{}L_{y^{\prime}}^{\top}q+v^{\top}q\big{)}$
$\displaystyle=\max_{y\in\mathcal{Y}}\big{(}\max_{q\in\Delta(y)}~{}L_{y}^{\top}q+v^{\top}q\big{)}$
$\displaystyle=\max_{y\in\mathcal{Y}}~{}(\Omega_{\operatorname{RM}}^{y})^{*}(v),$

where we have used the fact that
$\min_{y^{\prime}\in\mathcal{Y}}L_{y^{\prime}}^{\top}q=L_{y}^{\top}q$ whenever
$q\in\Delta(y)$ by construction. ∎

Moreover, it can be readily seen that $S_{\operatorname{RM}}(v,y)\leq
S_{\operatorname{MM}}(v,y)\leq S_{\operatorname{M}}(v,y)$, for all
$v\in\mathbb{R}^{k}$ and $y\in\mathcal{Y}$. See Fig. 1 (left and middle) and
Fig. 2 for the shape of these losses when $L$ is the 0-1 loss for two and
three dimensions, respectively. Our main quantity of interest is the Bayes
risk $H_{S}$, because by comparing it with $H_{L}$ we are able to tell whether
$L$ is embedded by $S$ using Prop. 3.2, thus proving consistency. The
following Prop. 3.4 gives the form of the Bayes risks.

######  Proposition 3.4 (Bayes risks).

For all $q\in\Delta$, the Bayes risks read

$\displaystyle H_{\operatorname{MM}}(q)$ $\displaystyle=H_{L}(q),$
$\displaystyle H_{\operatorname{M}}(q)$ $\displaystyle=\underset{Q\in
U(q,q)}{\max}\langle L,Q\rangle_{\operatorname{F}},$ $\displaystyle
H_{\operatorname{RM}}(q)$ $\displaystyle=\underset{Q\in
U(q,q)\cap\mathcal{C}_{L}}{\max}\langle L,Q\rangle_{\operatorname{F}},$

where $U(q,q)=\\{Q\in\mathbb{R}^{k\times k}~{}|~{}Q1=q,Q^{\top}1=q,Q\succeq
0\\}$, $\mathcal{C}_{L}=\\{Q\in\mathbb{R}^{k\times
k}~{}|~{}(1L_{y}^{\top}-L)Q_{y}\preceq 0,~{}\forall y\in\mathcal{Y}\\}$ and
$\langle\cdot,\cdot\rangle_{\operatorname{F}}$ denotes the Frobenius inner
product. Moreover, we have that $H_{\operatorname{RM}}\leq
H_{\operatorname{MM}}\leq H_{\operatorname{M}}$, and there exists $L$ for
which $H_{L}\neq H_{\operatorname{M}}$ and/or $H_{\operatorname{RM}}\neq
H_{L}$.

The proof can be found in Section 1 of Appendix. As a corollary, the only one
of these losses always embedding $L$ is the Max-Min-Margin loss. Our
sufficient conditions for consistency will correspond to the conditions on $L$
for which the Bayes risks $H_{\operatorname{M}}$ and/or
$H_{\operatorname{RM}}$ are equal (or proportional) to $H_{L}$, thus implying
consistency. In the next section, we use the expressions of the Bayes risks
given by Prop. 3.4 as a basis to prove the consistency results.

##  4 FISHER CONSISTENCY ANALYSIS

###  4.1 Analysis of Max-Margin Loss

In this section we want to provide a necessary condition for consistency of
the Max-Margin loss (Thm. 2.1). Note that it is not enough to provide a
condition for which $H_{S}\neq H_{L}$, as $S$ consistent to $L$ does not imply
$S$ embedding $L$. The following Prop. 4.1 gives a necessary condition for
consistency in terms of the extreme points of the prediction sets and the
Bayes risk of $S$.

######  Proposition 4.1.

Assume $S$ is Fisher consistent to $L$. Then, for any extreme point
$q\in\Delta$ of a prediction set $\Delta(y),~{}y\in\mathcal{Y}$, we
necessarily have $\\{q\\}=\partial(-H_{S})^{*}(v)$ for some
$v\in\mathbb{R}^{k}$.

The set $\partial h(x)$ denotes the subgradient of the function $h$. This
result is proven in Section 2 of Appendix. To use this necessary condition, we
first have to compute the Fenchel conjugate $(-H_{\operatorname{M}})^{*}$ of
the Max-Margin loss. This is given by the following Prop. 4.2.

######  Proposition 4.2.

If $L$ is symmetric, then

$(-H_{\operatorname{M}})^{*}(v)=\max_{y,y^{\prime}\in\mathcal{Y}}~{}L(y,y^{\prime})+\frac{v_{y}+v_{y^{\prime}}}{2},$

for all $v\in\mathbb{R}^{k}$.

As a corollary, we obtain the specific form of the images of the sub-gradient
mapping $\partial(-H_{\operatorname{M}})^{*}$ at the differentiable points,
i.e., when the sub-gradient is a singleton.

######  Corollary 4.3.

The $0$-dimensional images of $\partial(-H_{\operatorname{M}})^{*}$ are of the
form $q=\frac{1}{2}(e_{y}+e_{y^{\prime}}),y,y^{\prime}\in\mathcal{Y}$.

Figure 3: Left: Prediction sets $\Delta(y)$ for a symmetric loss. The points
given by Cor. 4.3 are the 3 extremes of the simplex and the middle points in
the faces of the simplex. The interior point is not of the form
$\frac{1}{2}(e_{y}+e_{y^{\prime}})$ for any $y,y^{\prime}\in\\{1,2,3\\}$.
Middle: The sufficient condition from Prop. 4.6 is satisfied for any point in
the simplex. Right: The sufficient condition from Prop. 4.6 is not satisfied
as the prediction set $\Delta(2)$ (in green) intersects the line $q_{2}=0$.
Moreover, inconsistency can be shown in this case by comparing the affine
regions of the Bayes risk $H_{\operatorname{RM}}$ with these predictions sets.

Note that the points
$\\{q\\}\in\operatorname{Im}\partial(-H_{\operatorname{M}})^{*}$ are
independent of the discrete loss $L$. In Fig. 3 (left), we show that this is
not the case for the extreme points of the prediction sets $\Delta(y)$’s of a
generic $L$. In this example, the points $\frac{1}{2}(e_{y}+e_{y^{\prime}})$’s
are extreme points of the prediction sets because $L$ is symmetric, but the
extreme point in the interior is not of this form. By moving this point to
$\frac{1}{2}(e_{1}+e_{3})$, we enforce $L(1,2)+L(2,3)=L(1,3)$, which
corresponds precisely to the necessary condition given by Thm. 2.1 when
$z=y_{2}$. The generic necessary condition is obtained by extending this
argument to consider all possibilities in larger output spaces. The full proof
can be found in Section 2 of Appendix.

##### Consistency of distances defined in trees.

This result is proved by showing $H_{\operatorname{M}}=2H_{L}$ ( $H_{S}\propto
H_{L}$ also implies consistency (Finocchiaro et al., 2019)) whenever $L$ is a
distance defined in a tree, and it is done by proving equality of the Fenchel
conjugates $(-H_{\operatorname{M}})^{*}=(-2H_{L})^{*}$. The proof is based on
the analysis of the extreme points of a certain polytope defined in terms of
$L$, and can be found in Section 2 of Appendix.

##### Partial positive results on consistency.

In this section, we generalize the well-known result by Liu (2007) which
states that the Max-Margin loss is consistent to the 0-1 loss under the
dominant label condition. More specifically, we provide a generalization of
this result to all distance losses, i.e., symmetric and satisfying the
triangle inequality.

######  Proposition 4.4.

If $L$ is a distance, then we have $H_{\operatorname{M}}\leq 2H_{L}$ and
$H_{\operatorname{M}}(q)=2H_{L}(q)$ ($S$ embeds $2L$, thus consistent), for
all $q\in\Delta$ such that $\max_{y\in\mathcal{Y}}q_{y}\geq 1/2$.

Some intuition can be obtained for $k=3$. The interior of the set delimited by
the dashed lines in the left image from Fig. 3 shows precisely the points
where $\max_{y\in\mathcal{Y}}~{}q_{y}\leq 1/2$. If $L$ is a distance, then the
interior extreme point can only move inside this region, and hence, it remains
consistent at the exterior of this set, which is precisely where the dominant
label condition is satisfied. The proof of this result can be found in Section
2 of Appendix.

###  4.2 Analysis of Restricted-Max-Margin Loss

In this section we sketch the proof of the consistency of the Restricted-Max-
Margin loss (Thm. 2.4). We prove that $S_{\operatorname{RM}}$ embeds $L$ by
showing equal Bayes risks using the expressions from Prop. 3.4. The proof is
done in two steps. In the first one (Prop. 4.5), we show that under a
condition on the extreme points of the prediction sets both Bayes risks are
equal, while in the second we obtain that this condition is satisfied whenever
the hypothesis from Thm. 2.4 holds.

######  Proposition 4.5.

If $qq^{\top}\in\mathcal{C}_{L}=\\{Q\in\mathbb{R}^{k\times
k}~{}|~{}(1L_{y}^{\top}-L)Q_{y}\preceq 0,~{}\forall y\in\mathcal{Y}\\}$ for
all extreme points $q\in\Delta$ of the prediction sets $\Delta(y)$’s, then
$H_{\operatorname{RM}}=H_{L}$.

###### Proof.

By Prop. 3.4, we already know that $H_{\operatorname{RM}}\leq H_{L}$, so we
only need to show that $H_{\operatorname{RM}}\geq H_{L}$. If $q$ is an extreme
point of the prediction set $\Delta(y)$, then $H_{\operatorname{RM}}(q)\geq
H_{L}(q)$ by taking the matrix $qq^{\top}\in U(q,q)\cap\mathcal{C}_{L}$, which
satisfies $\langle
L,qq^{\top}\rangle_{\operatorname{F}}=\sum_{y^{\prime}}q_{y^{\prime}}L_{y^{\prime}}^{\top}q\geq\sum_{y^{\prime}}q_{y^{\prime}}L_{y}^{\top}q=L_{y}^{\top}q=H_{L}(q)$,
where we have used that $L_{y^{\prime}}^{\top}q\geq L_{y}^{\top}q$ for all
$y^{\prime}\in\mathcal{Y}$ as $q\in\Delta(y)$. If $q$ is not an extreme point,
then it can be written as a convex combination of extreme points $q_{i}$ of
$\Delta(y)$ as $q=\sum_{i=1}^{m}\alpha_{i}q_{i}$ with
$\alpha^{\top}1=1,\alpha\succeq 0$. Then, it is straightforward to show that
the matrix $Q=\sum_{i=1}^{m}\alpha_{i}q_{i}q_{i}^{\top}$ is in
$U(q,q)\cap\mathcal{C}_{L}$, and satisfies $\langle
L,Q\rangle_{\operatorname{F}}\geq L_{y}^{\top}q=H_{L}(q)$. More details in
Section 3 of Appendix. ∎

######  Proposition 4.6.

Assume that for every $q\in\Delta$, if $y$ is optimal for $q$ (i.e.,
$q\in\Delta(y)$), then $q_{y}>0$. In this case, all extreme points of the
prediction sets satisfy $qq^{\top}\in\mathcal{C}_{L}$.

The proof of this result and the fact that consistency of
$S_{\operatorname{M}}$ implies consistency of $S_{\operatorname{RM}}$ can be
found in Section 3 of Appendix. In Fig. 3 (middle and right), we show
geometrically in dimension $k=3$ what this condition means.

###  4.3 Argmax Decoding

The positive consistency results of both $S_{\operatorname{M}}$ and
$S_{\operatorname{RM}}$ do not specify whether the argmax decoding
$d(v)=\operatorname*{arg\;max}_{y\in\mathcal{Y}}~{}v_{y}$ is consistent, but
just that there exists a decoding for which consistency holds. From Nowak-Vila
et al. (2020), we know that the set of minimizers of the Max-Min-Margin loss
$S_{\operatorname{MM}}$ is

$v_{\operatorname{MM}}^{\star}(q)=-\operatorname{hull}(L_{y})_{y\in
y^{\star}(q)}+\mathcal{N}_{\Delta}(q),$ (11)

for all $q\in\Delta$, where $\operatorname{hull}$ denotes the convex hull and
$\mathcal{N}_{\Delta}(q)=\\{u\in\mathbb{R}^{k}~{}|~{}u^{\top}(p-q)\leq
0,\forall p\in\Delta\\}$ is the normal cone of the simplex at the point $q$.
In this case, the argmax decoding is consistent because
$\operatorname*{arg\;max}_{y}v_{y}\in y^{\star}(q)$ whenever $v\in
v_{\operatorname{MM}}^{\star}(q)$ if Eq. 11 is satisfied. The following Thm.
4.7 shows that the same holds true for the other losses whenever they embed
$L$ (or $2L$).

######  Theorem 4.7.

$S_{\operatorname{M}}$ and $S_{\operatorname{RM}}$ are consistent to $L$ under
the argmax decoding whenever $H_{\operatorname{M}}=2H_{L}$
($S_{\operatorname{M}}$ embeds $2L$) and $H_{\operatorname{RM}}=H_{L}$
($S_{\operatorname{RM}}$ embeds $L$), respectively.

##  5 CONCLUSION AND FUTURE DIRECTIONS

In this work, we have analyzed the consistency properties of the well-known
Max-Margin loss for general classification tasks. We show that a restrictive
condition on the task, which is not satisfied by most of the used losses in
practice, is necessary for Fisher consistency. We also show consistency for
the absolute deviation loss used in ordinal regression, and more generally to
any distance defined in a tree, showing that the necessary condition is
meaningful. Moreover, we have overcome this limitation and introduced a novel
generalization of the binary SVM loss called Restricted-Max-Margin loss, which
maintains the maximization over the loss-augmented scores and it is consistent
under milder conditions on the task at hand. Two important questions remain
unanswered: first, whether the proposed necessary condition for the Max-Margin
is sufficient or not, and secondly, whether there exist tractable linear
maximization oracles over the prediction sets $\Delta(y)$ for specific
structured prediction problems, which would make the Restricted-Max-Margin
loss more attractive than the Max-Min-Margin loss in practice.

#### Acknowledgements

This work was funded in part by the French government under management of
Agence Nationale de la Recherche as part of the ‘Investissements d’avenir’
program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute). We acknowledge
support of the European Research Council (grant SEQUOIA 724063). We also
acknowledge support of the European Research Council (grant REAL 947908).

## References

  * Boser et al. (1992) Bernhard E Boser, Isabelle M Guyon, and Vladimir N Vapnik.  A training algorithm for optimal margin classifiers.  In _Proceedings of the fifth annual workshop on Computational learning theory_ , pages 144–152, 1992.
  * Cortes and Vapnik (1995) Corinna Cortes and Vladimir Vapnik.  Support-vector networks.  _Machine Learning_ , 20(3):273–297, 1995.
  * 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.
  * Taskar et al. (2004) Ben Taskar, Carlos Guestrin, and Daphne Koller.  Max-margin Markov networks.  In _Advances in Neural Information Processing Systems_ , pages 25–32, 2004.
  * Tsochantaridis et al. (2005) Ioannis Tsochantaridis, Thorsten Joachims, Thomas Hofmann, and Yasemin Altun.  Large margin methods for structured and interdependent output variables.  _Journal of Machine Learning Research_ , 6(Sep):1453–1484, 2005.
  * Liu (2007) Yufeng Liu.  Fisher consistency of multicategory support vector machines.  In _Artificial Intelligence and Statistics_ , pages 291–298, 2007\.
  * Taskar et al. (2005) Ben Taskar, Simon Lacoste-Julien, and Dan Klein.  A discriminative matching approach to word alignment.  In _Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing_ , pages 73–80, 2005.
  * Caetano et al. (2009) Tibério S. Caetano, Julian J. McAuley, Li Cheng, Quoc V. Le, and Alex J. Smola.  Learning graph matching.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 31(6):1048–1058, 2009.
  * Smith (2011) Noah A. Smith.  Linguistic structure prediction.  _Synthesis Lectures on Human Language Technologies_ , 4(2):1–274, 2011.
  * Fathony et al. (2016) Rizal Fathony, Anqi Liu, Kaiser Asif, and Brian Ziebart.  Adversarial multiclass classification: A risk minimization perspective.  In _Advances in Neural Information Processing Systems_ , pages 559–567, 2016.
  * 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.
  * Nowak-Vila et al. (2020) Alex Nowak-Vila, Francis Bach, and Alessandro Rudi.  Consistent structured prediction with max-min margin markov networks.  In _Proceedings of the International Conference on Machine Learning (ICML)_ , 2020.
  * Aronszajn (1950) Nachman Aronszajn.  Theory of reproducing kernels.  _Transactions of the American Mathematical Society_ , 68(3):337–404, 1950.
  * Vapnik (1992) Vladimir Vapnik.  Principles of risk minimization for learning theory.  In _Advances in Neural Information Processing Systems_ , pages 831–838, 1992.
  * Vapnik (2013) Vladimir Vapnik.  _The nature of statistical learning theory_.  Springer Science & Business Media, 2013.
  * 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.
  * Devroye et al. (2013) Luc Devroye, László Györfi, and Gábor Lugosi.  _A Probabilistic Theory of Pattern Recognition_ , volume 31.  Springer Science & Business Media, 2013.
  * Joachims (2006) Thorsten Joachims.  Training linear SVMs in linear time.  In _Proceedings of the SIGKDD International Conference on Knowledge Discovery and Data Mining_ , pages 217–226. ACM, 2006.
  * BakIr et al. (2007) Gökhan BakIr, Thomas Hofmann, Bernhard Schölkopf, Alexander J. Smola, Ben Taskar, and S.V.N. Vishwanathan.  _Predicting Structured Data_.  MIT press, 2007.
  * 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.
  * McAllester (2007) David McAllester.  Generalization bounds and consistency.  _Predicting Structured Data_ , pages 247–261, 2007.
  * Dogan et al. (2016) Ürün Dogan, Tobias Glasmachers, and Christian Igel.  A unified view on multi-class support vector classification.  _J. Mach. Learn. Res._ , 17(45):1–32, 2016.
  * Weston and Watkins (1999) Jason Weston and Chris Watkins.  Support vector machines for multi-class pattern recognition.  In _ESANN_ , volume 99, pages 219–224, 1999.
  * Lee et al. (2004) Yoonkyung Lee, Yi Lin, and Grace Wahba.  Multicategory support vector machines: Theory and application to the classification of microarray data and satellite radiance data.  _Journal of the American Statistical Association_ , 99(465):67–81, 2004.
  * Mroueh et al. (2012) Youssef Mroueh, Tomaso Poggio, Lorenzo Rosasco, and Jean-Jeacques Slotine.  Multiclass learning with simplex coding.  In _Advances in Neural Information Processing Systems_ , pages 2789–2797, 2012.
  * Petterson et al. (2009) James Petterson, Jin Yu, Julian J. McAuley, and Tibério S. Caetano.  Exponential family graph matching and ranking.  In _Advances in Neural Information Processing Systems_ , pages 1455–1463, 2009.
  * Tewari and Bartlett (2007) Ambuj Tewari and Peter L. Bartlett.  On the consistency of multiclass classification methods.  _Journal of Machine Learning Research_ , 8(May):1007–1025, 2007.
  * Finocchiaro et al. (2019) Jessica Finocchiaro, Rafael Frongillo, and Bo Waggoner.  An embedding framework for consistent polyhedral surrogates.  In _Advances in Neural Information Processing Systems_ , 2019.
  * Blondel et al. (2020) Mathieu Blondel, André FT Martins, and Vlad Niculae.  Learning with Fenchel-Young losses.  _Journal of Machine Learning Research_ , 21(35):1–69, 2020.
  * Rockafellar (1997) R Tyrrell Rockafellar.  Convex analysis. princeton landmarks in mathematics, 1997.
  * Andreasson et al. (2020) Niclas Andreasson, Michael Patriksson, and Anton Evgrafov.  _An Introduction to Continuous Optimization: Foundations and Fundamental Algorithms_.  Courier Dover Publications, 2020.

Supplementary Material:
On the Consistency of Max-Margin Losses

Outline. The supplementary material is organized as follows. In Appendix A, we
prove general results on embeddings of losses, we compute the Bayes risks for
each of the losses and we provide an algebraic characterization of the extreme
points of the prediction sets. In Appendix B and Appendix C, we provide the
main results of the Max-Margin loss and the Restricted-Max-Margin loss,
respectively.

##  Appendix A PRELIMINARY RESULTS

###  A.1 Results on Embeddability of Losses

######  Proposition A.1.

Let $\psi:\mathcal{Y}\xrightarrow[]{}\mathbb{R}^{k}$ be an embedding of the
output space. If $H_{S}=H_{L}$ and $S(\psi(y))=L_{y}$ for all
$y\in\mathcal{Y}$, then $S$ embeds $L$ with embedding $\psi$.

###### Proof.

To prove that $S$ embeds $L$ with embedding $\psi(y)=-L_{y}$, we need to show
that

$y\in y^{\star}(q)\iff\varphi(y)\in v^{\star}(q).$

If $y\in y^{\star}(q)$, then

$H_{L}(q)=~{}L_{y}^{\top}q=S(\varphi(y))^{\top}q=H(q)=\min_{v\in\mathbb{R}^{k}}~{}S(v)^{\top}q.$

Thus, $S(\varphi(y))^{\top}q=\min_{v\in\mathbb{R}^{k}}~{}S(v)^{\top}q$ implies
that necessarily $\varphi(y)\in v^{\star}(q)$. Similarly, if $\varphi(y)\in
v^{\star}(q)$, then $\min_{z}~{}L_{z}^{\top}q=L_{y}^{\top}q$ which implies
$y\in y^{\star}(q)$. ∎

###  A.2 Bayes risk identities

The following Lemma A.2 provides an identity which will be useful to provide
the forms of the Bayes risk for $S_{\operatorname{M}}$ and
$S_{\operatorname{RM}}$.

######  Lemma A.2.

Let $\mathcal{C}_{y}\subseteq\Delta$,
$\Omega^{y}(q)=-L_{y}^{\top}q+i_{\mathcal{C}_{y}}(q)$ and
$S(v,y)=(\Omega^{y})^{*}(v)-v_{y}$ for every $y\in\mathcal{Y}$. Then,

$H_{S}(q)=\max_{\begin{subarray}{c}\sum_{y}q_{y}\nu_{y}=q\\\
\nu_{y}\in\mathcal{C}_{y}\end{subarray}}~{}\sum_{y}q_{y}L_{y}^{\top}\nu_{y}.$
(12)

###### Proof.

Recall the definition of the Bayes risk
$H(q)=\min_{v\in\mathbb{R}^{k}}~{}S(v)^{\top}q$. Using the structural
assumption on $S$, we can re-write it as

$H(q)=\min_{v\in\mathbb{R}^{k}}~{}\sum_{y\in\mathcal{Y}}q_{y}(\Omega^{y})^{*}(v)-v^{\top}q=-\max_{v\in\mathbb{R}^{k}}~{}v^{\top}q-\sum_{y\in\mathcal{Y}}q_{y}(\Omega^{y})^{*}(v)=-\Big{(}\sum_{y\in\mathcal{Y}}q_{y}(\Omega^{y})^{*}\Big{)}^{*}(q).$

Recall that if the functions $h_{i}$ are convex, then the conjugate of the sum
is the infimum convolution of the individual conjugates (Rockafellar, 1997) as

$\Big{(}\sum_{i}h_{i}\Big{)}^{*}(t)=\min_{\sum_{i}x_{i}=t}\sum_{i}h_{i}^{*}(x_{i}).$

If we apply this property to the functions $h_{i}=q_{i}(\Omega^{y})^{*}$, we
obtain:

$\displaystyle-\Big{(}\sum_{y\in\mathcal{Y}}q_{y}(\Omega^{y})^{*}\Big{)}^{*}(q)$
$\displaystyle=-\min_{\sum_{y\in\mathcal{Y}}\nu_{y}=q}~{}\sum_{y\in\mathcal{Y}}(q_{y}(\Omega^{y})^{*})^{*}(\nu_{y})$
$\displaystyle=-\min_{\sum_{y\in\mathcal{Y}}\nu_{y}=q}~{}\sum_{y\in\mathcal{Y}}q_{y}\Omega^{y}(\nu_{y}/q_{y})$
$\displaystyle(ah)^{*}(x)=ah^{*}(x/a)$
$\displaystyle=-\min_{\begin{subarray}{c}\sum_{y\in\mathcal{Y}}\nu_{y}=q\\\
\nu_{y}/q_{y}\in\mathcal{C}_{y},~{}\forall
y\in\mathcal{Y}\end{subarray}}~{}-\sum_{y\in\mathcal{Y}}L_{y}^{\top}\nu_{y}$
$\displaystyle\Omega^{y}(q)=-L_{y}^{\top}q+i_{\mathcal{C}_{y}}(q)$
$\displaystyle=\max_{\begin{subarray}{c}\sum_{y\in\mathcal{Y}}\nu_{y}=q\\\
\nu_{y}/q_{y}\in\mathcal{C}_{y},~{}\forall
y\in\mathcal{Y}\end{subarray}}~{}\sum_{y\in\mathcal{Y}}L_{y}^{\top}\nu_{y}$
$\displaystyle\text{redefine }\nu_{y}\text{ as }\nu_{y}/q_{y}$
$\displaystyle=\max_{\begin{subarray}{c}\sum_{y\in\mathcal{Y}}q_{y}\nu_{y}=q\\\
\nu_{y}\in\mathcal{C}_{y},~{}\forall
y\in\mathcal{Y}\end{subarray}}~{}\sum_{y\in\mathcal{Y}}q_{y}L_{y}^{\top}\nu_{y}.$

∎

The following Prop. A.3 provides us with the first part of Proposition 3.4.

######  Proposition A.3 (Bayes risks).

For all $q\in\Delta$, the Bayes risks read

$\displaystyle H_{\operatorname{MM}}(q)$
$\displaystyle=\min_{y\in\mathcal{Y}}~{}L_{y}^{\top}q=H_{L}(q)$ $\displaystyle
H_{\operatorname{M}}(q)$ $\displaystyle=\underset{Q\in U(q,q)}{\max}\langle
L,Q\rangle_{\operatorname{F}}$ $\displaystyle H_{\operatorname{RM}}(q)$
$\displaystyle=\underset{Q\in U(q,q)\cap\mathcal{C}_{L}}{\max}\langle
L,Q\rangle_{\operatorname{F}},$

where

$U(q,q)=\\{Q\in\mathbb{R}^{k\times k}_{+}~{}|~{}Q1=q,Q^{\top}1=q\\},\hskip
8.5359pt\text{and}\hskip 8.5359pt\mathcal{C}_{L}=\\{Q\in\mathbb{R}^{k\times
k}~{}|~{}(1L_{y}^{\top}-L)Q_{y}\preceq 0,~{}\forall y\in\mathcal{Y}\\}.$

###### Proof.

The first identity is trivial and has already been derived in the main body of
the paper. We use the above Lemma A.2 to obtain the identities corresponding
to $S_{\operatorname{M}}$ and $S_{\operatorname{RM}}$.

  1. 1.

_Bayes risk of Max-Margin:_ In this case $\mathcal{C}_{y}=\Delta$. If we
define $\Gamma\in\mathbb{R}^{k\times k}$ as the matrix whose rows are
$\nu_{y}$, the maximization reads

$\max_{\begin{subarray}{c}\Gamma^{\top}q=q\\\ \Gamma 1=1\\\ \Gamma\succeq
0\end{subarray}}~{}\sum_{y\in\mathcal{Y}}q_{y}L_{y}^{\top}\Gamma_{y}$

If we now define $Q\in\mathbb{R}^{k\times k}$ as
$Q=\operatorname{diag}(q)\Gamma$, i.e., $Q_{y}=q_{y}\Gamma_{y}$, the objective
can be re-written as a matrix scalar product as

$\sum_{y\in\mathcal{Y}}q_{y}L_{y}^{\top}\Gamma_{y}=\sum_{y\in\mathcal{Y}}L_{y}^{\top}(q_{y}\Gamma_{y})=\sum_{y\in\mathcal{Y}}L_{y}^{\top}Q_{y}=\langle
L,Q\rangle_{\operatorname{F}}.$

Whenever $q_{y}>0$, the change of variables $Q_{y}=q_{y}\Gamma_{y}$ is
invertible and the constraints satisfy

$\displaystyle(Q^{\top}1)_{y}=q_{y}$
$\displaystyle\iff(\Gamma^{\top}q)_{y}=q_{y}$ (13)
$\displaystyle(Q1)_{y}=q_{y}$ $\displaystyle\iff(\Gamma 1)_{y}=1$ (14)
$\displaystyle Q_{y}\succeq 0$ $\displaystyle\iff\Gamma_{y}\succeq 0.$ (15)

On the other hand, if $q_{y}=0$ then $Q_{y}=0$ but the objective is not
affected as it is independent of $\Gamma_{y}$.

  2. 2.

_Bayes risk of Restricted-Max-Margin:_ In this case
$\mathcal{C}_{y}=\Delta(y)=\\{q\in\Delta~{}|~{}(L_{y}-L_{y^{\prime}})^{\top}q\preceq
0,\forall y^{\prime}\in\mathcal{Y}\\}$. The maximization now reads

$\max_{\begin{subarray}{c}\Gamma^{\top}q=q\\\ \Gamma 1=1\\\ \Gamma\succeq 0\\\
(1L_{y}^{\top}-L)\Gamma_{y}\preceq 0,\forall
y\end{subarray}}~{}\sum_{y\in\mathcal{Y}}q_{y}L_{y}^{\top}\Gamma_{y}.$

The result follows as $(1L_{y}^{\top}-L)\Gamma_{y}\preceq 0$ if and only if
$(1L_{y}^{\top}-L)Q_{y}\preceq 0$ whenever $q_{y}>0$.

∎

###  A.3 Extreme points of a polytope

We will need to analyse the extreme points of the polytope
$\mathcal{P}=\\{(q,u)\in\mathbb{R}^{k+1}~{}|~{}q\in\Delta,L_{y}^{\top}q\geq
u,\forall y\in\mathcal{Y}\\}\subseteq\mathbb{R}^{k+1}$ in the proof of the
sufficient condition for consistency of Max-Margin in Sec. B.3.

Algebraic characterization of extreme points of a polyhedron.  The following
Prop. A.4 provides us with an algebraic characterization of the extreme points
of a polyhedron $\mathcal{Q}=\\{x\in\mathbb{R}^{n}~{}|~{}Ax\succeq b\\}$.

######  Proposition A.4 (Theorem 3.17 in Andreasson et al. (2020)).

Let $x\in\mathcal{Q}=\\{x\in\mathbb{R}^{n}~{}|~{}Ax\succeq b\\}$, where
$A\in\mathbb{R}^{m\times n}$ has $\operatorname{rank}(A)=n$ and
$b\in\mathbb{R}^{m}$. Let $I\subseteq[m]$ be a set of indexes for which the
subsystem is an equality, i.e., $A_{I}x_{I}=b_{I}$ with $Ax_{I}\succeq b$.
Then $x_{I}$ is an extreme point of $\mathcal{Q}$ if and only if
$\operatorname{rank}(A_{S})=n$.

Let $\mathcal{P}\subseteq\mathbb{R}^{k+1}$ be the polyhedron defined as

$\mathcal{P}=\\{(q,u)\in\mathbb{R}^{k+1}~{}|~{}q\in\Delta,L_{y}^{\top}q\geq
u,\forall y\in\mathcal{Y}\\}\subseteq\mathbb{R}^{k+1}.$

The polyhedron $\mathcal{P}$ can be written as
$\mathcal{P}=\\{x=(q,u)\in\mathbb{R}^{k+1}~{}|~{}Ax\succeq b\\}$ where

$\begin{array}[]{l}\begin{array}[]{c}\\\ \\\ S\\\ \\\ \end{array}\\\ \begin{array}[]{c}\\\ \\\ T\\\ \\\ \end{array}\\\ \begin{array}[]{c}\\\ \\\ \end{array}\end{array}\begin{array}[]{l}\left\\{\begin{array}[]{c}\\\ \\\ \\\ \\\ \end{array}\right.\\\ \left\\{\begin{array}[]{c}\\\ \\\ \\\ \\\ \end{array}\right.\\\ \begin{array}[]{c}\\\ \\\ \end{array}\end{array}\underbrace{\left(\begin{array}[]{c | c}\begin{array}[]{ccc}&&\\\ &\text{{L}}&\\\ &&\\\ \end{array}&\begin{array}[]{c}\vdots\\\ -1\\\ \vdots\\\ \end{array}\\\ \hline\cr\begin{array}[]{ccc}&&\\\ &\text{{Id}}&\\\ &&\\\ \end{array}&\begin{array}[]{c}\vdots\\\ 0\\\ \vdots\\\ \end{array}\\\ \hline\cr\begin{array}[]{ccc}\cdots&1&\cdots\\\ \end{array}&0\\\ \begin{array}[]{ccc}\cdots&-1&\cdots\\\ \end{array}&0\\\ \end{array}\right)}_{A}\left(\begin{array}[]{c}\\\ \\\ q\\\ \\\ \\\ \hline\cr u\end{array}\right)\succeq\underbrace{\left(\begin{array}[]{c}\vdots\\\ 0\\\ \vdots\\\ \hline\cr\vdots\\\ 0\\\ \vdots\\\ \hline\cr 1\\\ -1\end{array}\right)}_{b},$ (16)

with $A\in\mathbb{R}^{(2k+2)\times(k+1)}$ and $b\in\mathbb{R}^{k+1}$. Note
that $\operatorname{rank}(A)=k+1$. Given $x=(q,u)$, define
$S,T\subseteq\mathcal{Y}$ as the subsets of outputs such that

$y\in S\iff L_{y}^{\top}q=u,\hskip 14.22636pty\in T\iff q_{y}=0,$ (17)

i.e., $S$ and $T$ correspond to the indexes of the first and second block of
the matrix $A$ for which the inequality holds as an equality, respectively.
More concretely, if $I$ are the indices of $A$ for which $A_{I}x_{I}=b_{I}$,
we have that $I=S\cup(k+T)\cup\\{2k+1\\}\cup\\{2k+1\\}$, because the last two
inequalities must be an equality as $q\in\Delta$. Moreover, the sets $S$ have
the following properties:

  * -

We necessarily have $|S|\geq 1$: if $S=\emptyset$, then
$\operatorname{rank}(A_{I})=k$ and so the rank is not maximal, thus $x=(q,u)$
cannot be an extreme point.

  * -

We necessarily have $|S|+|T|\geq k$ (using the fact that
$\operatorname{rank}(A)=k+1$).

##  Appendix B RESULTS ON MAX-MARGIN LOSS

###  B.1 Bayes Risk of Max-Margin for Symmetric Losses

The following Prop. B.1 gives another expression of the Bayes risk of
$S_{\operatorname{M}}$ and its Fenchel conjugate assuming the loss $L$ is
symmetric.

######  Proposition B.1.

Let $H_{\operatorname{M}}(q)=\max_{Q\in U(q,q)}~{}\langle
L,Q\rangle_{\operatorname{F}}$ and assume $L$ symmetric. Then, the following
identities hold:

$\displaystyle H_{\operatorname{M}}(q)$
$\displaystyle=\min_{\frac{1}{2}(a_{y}+a_{y^{\prime}})\geq
L(y,y^{\prime})}~{}a^{\top}q,\hskip 14.22636pt\forall q\in\Delta,$ (18)
$\displaystyle(-H_{\operatorname{M}})^{*}(v)$
$\displaystyle=\max_{y,y^{\prime}\in\mathcal{Y}}~{}L(y,y^{\prime})+\frac{v_{y}+v_{y^{\prime}}}{2},\hskip
14.22636pt\forall v\in\mathbb{R}^{k}.$ (19)

###### Proof.

The first part corresponds to the dual of the maximization problem defining
the Bayes risk $H_{\operatorname{M}}$ when $L$ is symmetric:

$\displaystyle-\min_{Q\in U(q,q)}-\langle L,Q\rangle_{\operatorname{F}}$
$\displaystyle=\min_{Q\succeq
0}\max_{a,b\in\mathbb{R}^{k}}~{}a^{\top}(Q1-q)+b^{\top}(Q^{\top}1-q)-\langle
L,Q\rangle_{\operatorname{F}}$
$\displaystyle=-\max_{a,b\in\mathbb{R}^{k}}-a^{\top}q-b^{\top}q+\min_{Q\succeq
0}~{}a^{\top}Q1+b^{\top}Q^{\top}1-\langle L,Q\rangle_{\operatorname{F}}$

We can now re-write the minimization objective as a matrix scalar product with
$Q$ as
$a^{\top}Q1=\operatorname{Tr}(a^{\top}Q1)=\operatorname{Tr(Q1a^{\top})}=\langle
Q,a1^{\top}\rangle_{\operatorname{F}}$ and analogously $b^{\top}Q1=\langle
Q,1b^{\top}\rangle_{\operatorname{F}}$. Hence, the objective of the minimum
becomes $\langle a1^{\top}+1b^{\top}-L,Q\rangle_{\operatorname{F}}$, which
gives

$\min_{Q\succeq 0}~{}\langle
a1^{\top}+1b^{\top}-L,Q\rangle_{\operatorname{F}}=\left\\{\begin{array}[]{ll}0&\text{if}~{}a1^{\top}+1b^{\top}-L\succeq
0\\\ -\infty&\text{otherwise}\end{array}\right..$

We obtain the following minimization problem in $a,b\in\mathbb{R}^{k}$

$-\max_{a1^{\top}+1b^{\top}\succeq
L}-(a+b)^{\top}q=\min_{a1^{\top}+1b^{\top}\succeq L}~{}(a+b)^{\top}q.$

Using that $L$ is symmetric, we can add the constraint $a=b$. In order to see
this, let $(a^{\star},b^{\star})$ be a solution of the linear problem. If $L$
is symmetric, then $(b^{\star},a^{\star})$ is also a solution, which implies
that $\frac{1}{2}(a^{\star}+b^{\star},a^{\star}+b^{\star})$ too. Hence, we can
assume $a=b$ and we obtain the desired result.

For the second part, note that if $L$ is symmetric, the matrix $Q$ can be
assumed also symmetric. To see this, let
$Q^{\star}=\operatorname*{arg\;max}_{Q\in U(q,q)}\langle
L,Q\rangle_{\operatorname{F}}$. Then if $L$ symmetric $(Q^{\star})^{\top}$ is
also a solution, which means that $\frac{1}{2}(Q^{\star}+(Q^{\star})^{\top})$
too, which is symmetric. Hence, we can write

$\displaystyle H_{\operatorname{M}}(q)$
$\displaystyle=\max_{\begin{subarray}{c}Q=Q^{\top}\\\ Q1=q\\\ Q\succeq
0\end{subarray}}~{}\langle L,Q\rangle_{\operatorname{F}}$
$\displaystyle=\min_{v\in\mathbb{R}^{k}}\max_{\begin{subarray}{c}Q=Q^{\top}\\\
Q\in\operatorname{Prob}(\mathcal{Y}\times\mathcal{Y})\end{subarray}}~{}\langle
L,Q\rangle_{\operatorname{F}}-v^{\top}(Q1-q)$
$\displaystyle=\min_{v\in\mathbb{R}^{k}}\Big{\\{}\underbrace{\max_{\begin{subarray}{c}Q=Q^{\top}\\\
Q\in\operatorname{Prob}(\mathcal{Y}\times\mathcal{Y})\end{subarray}}~{}\langle
L+v1^{\top},Q\rangle_{\operatorname{F}}}_{(-H_{\operatorname{M}})^{*}(v)}\Big{\\}}-v^{\top}q,$

where at the last step we have used that $q\in\Delta$ and so $1^{\top}Q1=1$,
which together with $Q\succeq 0$ implies
$Q\in\operatorname{Prob}(\mathcal{Y}\times\mathcal{Y})$. The extreme points of
the problem domain
$\\{Q\in\operatorname{Prob}(\mathcal{Y}\times\mathcal{Y})\\}$ where the
maximization of the linear objective is achieved are precisely the points
$\\{\frac{1}{2}(e_{y}+e_{y^{\prime}})\\}_{y,y^{\prime}\in\mathcal{Y}}$. ∎

###  B.2 Necessary Conditions for Consistency

Recall that $S$ is consistent to $L$ if there exists a decoding
$d:\mathbb{R}^{k}\xrightarrow[]{}\mathcal{Y}$ such that if $v\in
v^{\star}(q)$, then necessarily $d(v)\in y^{\star}(q)$ for all $q\in\Delta$. A
necessary condition for this to hold is that every level set of $v^{\star}$
must be included in a level set of $y^{\star}$, which are precisely the
prediction sets.

######  Lemma B.2.

If $S$ is consistent to $L$, then for every $v\in\mathbb{R}^{k}$ there must
exist a $y\in\mathcal{Y}$ such that

$(v^{\star})^{-1}(v)\subseteq(y^{\star})^{-1}(y)=\Delta(y).$ (20)

###### Proof.

If (20) does not hold, then there exists $q_{1},q_{2}\in(v^{\star})^{-1}(v)$
with $y^{\star}(q_{1})\cap y^{\star}(q_{2})=\emptyset$. However, Fisher
consistency means that $v\in v^{\star}(q_{1})$ implies $d(v)\in
y^{\star}(q_{1})$ and $v\in v^{\star}(q_{2})$ implies $d(v)\in
y^{\star}(q_{2})$, which is not possible because $y^{\star}(q_{1})\cap
y^{\star}(q_{2})=\emptyset$. ∎

The following Cor. B.4 re-writes (20) in terms of the Bayes risk $H_{S}$.

######  Proposition B.3.

The level sets of $v^{\star}$ are the image of
$-\partial(-H_{S})^{*}:\mathbb{R}^{k}\xrightarrow[]{}2^{\Delta}$, i.e.,

$\operatorname{Im}((v^{\star})^{-1})=\operatorname{Im}(-\partial(-H_{S})^{*}).$
(21)

###### Proof.

First of all, note that $-\partial(-H_{S})^{*}=(\partial
H_{\operatorname{M}})^{-1}$ (Rockafellar, 1997). We have

$H_{S}(q)=\min_{v\in\mathbb{R}^{k}}~{}S(v)^{\top}q+i_{\Delta}(q),\hskip
14.22636pt\partial H_{S}(q)=S(\bar{v})+\langle 1\rangle,~{}\bar{v}\in
v^{\star}(q).$

Let’s now prove the two inclusions.

($\subseteq$): Let $Q\in\operatorname{Im}((v^{\star})^{-1})$. This means that
there exists $V\in\mathbb{R}^{k}$ such that
$V=\operatorname*{arg\;min}_{v\in\mathbb{R}^{k}}~{}S(v)^{\top}q$ for all $q\in
Q$. If we define $T=S(V)+\langle 1\rangle$, then $T=\partial
H_{\operatorname{M}}(q)$ for all $q\in Q$.

($\supseteq$): Let $Q\in\operatorname{Im}((\partial
H_{\operatorname{M}})^{-1})$. This means that there exists $T$ such that
$T=\partial H_{\operatorname{M}}(q)$ for all $q\in Q$. For every $q\in Q$, the
set $T$ can be written as $T=S(v^{\star}(q))+\langle 1\rangle$. To show that
$v^{\star}(q)=v^{\star}(q^{\prime})$ for all $q,q^{\prime}\in Q$, we need to
show that if $S(v)=S(v^{\prime})+c1,v\in v^{\star}(q),v^{\prime}\in
v^{\star}(q^{\prime})$ for some $q,q^{\prime}\in Q$, then necessarily $c=0$.
This is because $S(v(q))^{\top}q^{\prime}\geq
S(v(q^{\prime}))^{\top}q^{\prime}\implies c\geq 0$ and $S(v(q))^{\top}q\leq
S(v(q^{\prime}))^{\top}q\implies c\leq 0$.

∎

######  Corollary B.4 (Necessary condition for consistency).

If $S$ is Fisher consistent to $L$, then for every $v\in\mathbb{R}^{k}$, there
exists $y\in\mathcal{Y}$ such that

$-\partial(-H_{S})^{*}(v)\subseteq\Delta(y).$ (22)

###### Proof.

This follows directly from Eq. 20 and Prop. B.3. ∎

######  Proposition B.5 (Weaker necessary condition for consistency).

If $S$ is consistent to $L$, then every extreme point of $\Delta(y)$ for some
$y\in\mathcal{Y}$ must be a 0-dimensional image of $-\partial(-H_{S})^{*}$.

###### Proof.

Let $\Delta_{S}(v)=-\partial(-H_{S})^{*}(v)$. There exists a finite set
$\mathcal{V}\subseteq\mathbb{R}^{k}$ such that
$\bigcup_{v\in\mathcal{V}}\Delta_{S}(v)=\Delta(y)$. In particular, if $q$ is
an extreme point of $\Delta(y)$, then there exists $v\in\mathcal{V}$ such that
$q\in\Delta_{S}(v)$. We need to show that $q$ is also an extreme point of
$\Delta_{S}(v)$. Indeed, if $\Delta_{S}(v)\subseteq\Delta(y)$ are polyhedrons
and $q\in\Delta_{S}(v),\Delta(y)$ is an extreme point of $\Delta(y)$, then it
is also necessarily an extreme point of $\Delta_{S}(v)$. ∎

######  Theorem B.6.

Let $L$ be a symmetric loss with $k>2$. If the Max-Margin loss is consistent
to $L$, then $L$ is a distance, and for every three outputs
$y_{1},y_{2},y_{3}\in\mathcal{Y}$, there exists $z\in\mathcal{Y}$ for which
these the following three identities are satisfied:

$\displaystyle L(y_{1},y_{2})$ $\displaystyle=L(y_{1},z)+L(z,y_{2}),$
$\displaystyle L(y_{1},y_{3})$ $\displaystyle=L(y_{1},z)+L(z,y_{3}),$
$\displaystyle L(y_{2},y_{3})$ $\displaystyle=L(y_{2},z)+L(z,y_{3}).$

###### Proof.

Figure 4: These are the only possible possibilities of the prediction sets in
a three-dimensional face of the simplex. The equations associated to each
configuration is written below the corresponding simplex and all together can
be compactly written as the necessary condition given by the theorem. An edge
from a corner of the simplex to the middle point of the opposite side is not
possible as $L(y,y^{\prime})=0$ if and only if $y=y^{\prime}$ by assumption.

From Prop. B.1 and Prop. B.5, we obtain that if the Max-Margin loss is
consistent to $L$, then the extreme points of the prediction sets
$\Delta(y)$’s have to be of the form $1/2(e_{y}+e_{y^{\prime}})$. Hence, the
projection of the sets $\Delta(y)$’s into a three-dimensional simplex can only
be of the form depicted in Fig. 4. The necessary condition follows directly
from these possibilities (see caption of Fig. 4). Moreover, note that if the
three identities of the theorem hold, then $L$ is a distance. To see that,
note that the triangle inequality holds for any triplet
$y_{1},y_{2},y_{3}\in\mathcal{Y}$ as:

$\displaystyle L(y_{1},y_{2})$ $\displaystyle=L(y_{1},z)+L(z,y_{2})$
$\displaystyle=L(y_{1},y_{3})-L(z,y_{3})+L(y_{3},y_{2})-L(y_{3},z)$
$\displaystyle=L(y_{1},y_{3})+L(y_{3},y_{1})-2L(y_{3},z)$ $\displaystyle\leq
L(y_{1},y_{3})+L(y_{3},y_{1}).$

∎

##### Examples of losses not satisfying the necessary condition.

We now show that the examples exposed in Section 2 do not satisfy the
necessary condition of Thm. B.6.

######  Lemma B.7.

Let $L$ such with full rank loss matrix $L$ and existing
$q\in\operatorname{int}(\Delta)$ for which all outputs optimal, i.e.,
$y^{\star}(q)=\mathcal{Y}$. Then, the Max-Margin loss is _not_ consistent to
$L$.

###### Proof.

The point $q$, which is not of the form $1/2(e_{y}+e_{y^{\prime}})$ for some
$y,y^{\prime}\in\mathcal{Y}$, is an extreme point of the polytope
$\Delta(y)=\\{q\in\Delta~{}|~{}L_{z}^{\top}q\geq L_{y}^{\top}q,\forall
z\in\mathcal{Y}\\}$ for every $y\in\mathcal{Y}$. This is because $q\in\Delta$
is the unique solution of $Lq=u$ with $u=L_{y}^{\top}q$ for all
$y\in\mathcal{Y}$. Hence, by Prop. B.5, the Max-Margin loss is not consistent
to $L$. ∎

######  Lemma B.8.

The Max-Margin loss is not consistent to the the Hamming loss on permutations
$L(\sigma,\sigma^{\prime})=\frac{1}{M}\sum_{m=1}^{M}1(\sigma(m)\neq\sigma^{\prime}(m))$
where $\sigma,\sigma^{\prime}$ permutations of size $M$.

###### Proof.

Take the transpositions $\sigma_{1}=(3,2),\sigma_{2}=(2,1),\sigma_{3}=(3,1)$.
We have that $L(\sigma_{i},\sigma_{j})=2/M$ for $i\neq j$ and
$L(\sigma,\sigma^{\prime})>\frac{2}{M}$ for all permutations
$\sigma\neq\sigma^{\prime}$. Hence, the necessary condition can’t be
satisfied. ∎

##### The Hamming loss with $\boldsymbol{M=k=2}$ is consistent and it is not
defined in a tree.

The Hamming loss $L(y,y^{\prime})=\frac{1}{2}(1(y_{1}\neq
y_{1}^{\prime})+1(y_{2}\neq y_{2}^{\prime}))$ is consistent as it decomposes
additively and each term is consistent as it is the binary 0-1 loss. However,
it can’t be described as the shortest path distance in a tree, but rather the
shortest path distance in a cycle of size four with all weights equal to
$1/2$.

Figure 5: Left: The 4-partition of the output space where
$y_{1},y_{2},y_{3}\in S$. The different sets only communicate through the
edges $z_{i}-y_{i}$ for $i=1,2,3$ respectively. Right: The 3-partition of the
output space where $s_{1},s_{2}\in S$ and the depicted path is the path
between these two points.

###  B.3 Sufficient condition on the discrete loss L

######  Theorem B.9.

If $L$ is a distance defined in a tree, then the Max-Margin loss
$S_{\operatorname{M}}$ embeds $L$ with embedding $\psi(y)=-L_{y}$ and it is
consistent under the argmax decoding.

###### Proof.

We just have to prove that the extremes points of the polytope $\mathcal{P}$
defined as

$\mathcal{P}=\\{(q,u)\in\mathbb{R}^{k+1}~{}|~{}q\in\Delta,L_{y}^{\top}q\geq
u,\forall y\in\mathcal{Y}\\}\subseteq\mathbb{R}^{k+1}$

are of the form
$(\frac{1}{2}(e_{y}+e_{y^{\prime}}),\frac{1}{2}L(y,y^{\prime}))$, where
$y,y^{\prime}\in\mathcal{Y}$. Using this, we obtain

$\displaystyle(-H_{2L})^{*}(v)$
$\displaystyle=\max_{q\in\Delta}\min_{z\in\mathcal{Y}}~{}2L_{z}^{\top}q+v^{\top}q$
$\displaystyle=\max_{(q,u)\in\mathcal{P}}~{}2u+v^{\top}q$
$\displaystyle=\max_{(q,u)\in\operatorname{ext}(\mathcal{P})}~{}2u+v^{\top}q$
$\displaystyle=\max_{y,y^{\prime}\in\mathcal{Y}}~{}L(y,y^{\prime})+\frac{v_{y}+v_{y^{\prime}}}{2}=(-H_{\operatorname{M}})^{*}(v),$

for all $v\in\mathbb{R}^{k}$. This implies
$H_{2L}=2H_{L}=H_{\operatorname{M}}$. We will use the algebraic framework
introduced in Sec. A.3.

Let $x\in\operatorname{ext}(\mathcal{P})$ and $S$ are $T$ the sets of indices
for which $L_{y}^{\top}q=u$ and $q_{y^{\prime}}=0$ for $y\in S$ and
$y^{\prime}\in T$ (as defined in (17)).

If $|S|=1$, then we necessarily. have $|T|=k-1$ because $|T|\geq k-|S|=k-1$
and $|T|=k$ is not possible because $q$ is in the simplex. In this case, the
extreme point is equal to $q=(e_{y},0)$, which is of the desired form.

First part of the proof.  If $|S|\geq 2$, let’s prove that the elements in $S$
must be necessarily aligned, i.e., contained in a chain (always true for
$|S|=2$). If we denote by
$\operatorname{SP}(s,s^{\prime})\subseteq\mathcal{Y}$ the elements in the
shortest path between $s,s^{\prime}$, this means that there exists
$s_{1},s_{2}\in S$ such that $s\in\operatorname{SP}(s_{1},s_{2})$ for all
$s\in S$.

If the elements in $S$ are not aligned, then there exist pairwise different
elements $y_{1},y_{2},y_{3}\in S$ and $z_{1},z_{2},z_{3}\in\mathcal{Y}$
(possibly repeated) such that the tree defining the loss $L$ can be
partitioned into four sets
$\operatorname{I},\operatorname{II},\operatorname{III},\operatorname{IV}$ of
the form depicted in the left Fig. 5, where the edges $y_{i}-z_{i}$ belong to
the tree for $i=1,2,3$.

$\displaystyle L_{z_{1}}^{\top}q$
$\displaystyle=\sum_{y\in\operatorname{I}}~{}L(z_{1},y)q_{y}+\sum_{\begin{subarray}{c}y\notin\operatorname{I}\\\
y\neq z_{1}\end{subarray}}~{}L(z_{1},y)q_{y}$
$\displaystyle=\sum_{y\in\operatorname{I}}~{}(L(z_{1},y_{1})+L(y_{1},y))q_{y}+\sum_{\begin{subarray}{c}y\notin\operatorname{I}\\\
y\neq z_{1}\end{subarray}}~{}(L(y_{1},y)-L(z_{1},y_{1}))q_{y}$
$\displaystyle=\sum_{y\neq
z_{1}}~{}L(y_{1},y)q_{y}+\Big{(}\sum_{y\in\operatorname{I}}q_{i}-\sum_{\begin{subarray}{c}y\notin\operatorname{I}\\\
i\neq z_{1}\end{subarray}}q_{y}\Big{)}L(z_{1},y_{1})$
$\displaystyle=\sum_{y\in\mathcal{Y}}~{}L(y_{1},y)q_{y}+\Big{(}\sum_{y\in\operatorname{I}}q_{i}-\sum_{y\notin\operatorname{I}}q_{y}\Big{)}L(z_{1},y_{1})$
$\displaystyle=u+\Big{(}\sum_{y\in\operatorname{I}}q_{y}-\sum_{y\notin\operatorname{I}}q_{y}\Big{)}L(z_{1},y_{1}).$

If we repeat the same procedure for $\operatorname{II}$ and
$\operatorname{III}$, we obtain that

$\left\\{\begin{array}[]{ll}L_{z_{1}}^{\top}q&=u+\Big{(}\sum_{y\in\operatorname{I}}q_{y}-\sum_{y\notin\operatorname{I}}q_{y}\Big{)}L(z_{1},y_{1})\\\
L_{z_{2}}^{\top}q&=u+\Big{(}\sum_{y\in\operatorname{II}}q_{y}-\sum_{y\notin\operatorname{II}}q_{y}\Big{)}L(z_{2},y_{2})\\\
L_{z_{3}}^{\top}q&=u+\Big{(}\sum_{y\in\operatorname{III}}q_{y}-\sum_{y\notin\operatorname{III}}q_{y}\Big{)}L(z_{3},y_{3})\end{array}\right.$

However, note that
$\sum_{y\in\operatorname{I}}q_{y}+\sum_{y\in\operatorname{II}}q_{y}+\sum_{y\in\operatorname{III}}q_{y}+\sum_{y\in\operatorname{IV}}q_{y}=1$,
which implies that

$\min_{\mathcal{A}\in\\{\operatorname{I},\operatorname{II},\operatorname{III}\\}}~{}\Big{(}\sum_{y\in\mathcal{A}}q_{y}-\sum_{y\notin\mathcal{A}}q_{y}\Big{)}<0.$

Hence, there exists $i\in\\{1,2,3\\}$ for which $L_{z_{i}}^{\top}q<u$, which
leads to a contradiction as $L_{y}^{\top}q\geq u$ for all $y\in\mathcal{Y}$.

Second part of the proof. Now that we have that the elements in $S$ must be
aligned, let’s proceed with the proof by analyzing separately particular
cases:

  * -

($\boldsymbol{S\cap T=\emptyset}$): This means that $q_{s}>0$ for all $s\in
S$. Let $x=(\frac{1}{2}(e_{s_{1}}+e_{s_{2}}),\frac{1}{2}L(s_{1},s_{2}))$,
where $S\subseteq\operatorname{SP}(s_{1},s_{2})$. Then, it satisfies the
equality constraints as $L_{s}q=1/2(L(s_{1},s)+L(s,s_{2}))=1/2L(s_{1},s_{2})$
because $s\in\operatorname{SP}(s_{1},s_{2})$ for all $s\in S$. Hence, it has
to be equal to the unique solution of the linear system of equations.

  * -

($\boldsymbol{S\cap T\neq\emptyset}$): Let’s separate into two more cases.

    * –

($\boldsymbol{\exists r_{1},r_{2}\in[k]\setminus T}$ such that
$\boldsymbol{S\subseteq\operatorname{SP}(r_{1},r_{2})}$): Let
$x=(\frac{1}{2}(e_{r_{1}}+e_{r_{2}}),\frac{1}{2}L(r_{1},r_{2}))$. Then, it
satisfies the equality constraints as
$L_{s}q=1/2(L(r_{1},s)+L(s,r_{2}))=1/2L(r_{1},r_{2})$ because
$s\in\operatorname{SP}(r_{1},r_{2})$ for all $s\in S$. Hence, it has to be
equal to the unique solution of the linear system of equations.

    * –

($\boldsymbol{\nexists r_{1},r_{2}\in[k]\setminus T}$ such that
$\boldsymbol{S\subseteq\operatorname{SP}(r_{1},r_{2})}$): We will show that
this case is not possible. Consider the shortest path between $s_{1}$ and
$s_{2}$ in $S$ and the partition of the vertices of the tree into the sets
$\operatorname{I},\operatorname{II},\operatorname{III}$ depicted in the right
Fig. 5. We know that

$\\{\operatorname{I}\cap([k]\setminus
T)=\emptyset\\}\vee\\{\operatorname{II}\cap([k]\setminus T)=\emptyset\\}.$

If this is not true, then taking $r_{1}\in\operatorname{I}$ and
$r_{2}\in\operatorname{II}$ we obtain
$S\subseteq\operatorname{SP}(r_{1},r_{2})$. Assume that
$\operatorname{I}\cap([k]\setminus T)=\emptyset$. We have that
$L(s_{1},y)>L(\bar{s}_{1},y)$ for all $y\in[k]\setminus T$, which means that

$L_{s_{1}}^{\top}q>L_{\bar{s}_{1}}^{\top}q.$

This is a contradiction because $L_{y}^{\top}q\geq u=L_{s_{1}}^{\top}q$ as
$s_{1}\in S$. The case $\operatorname{II}\cap([k]\setminus T)=\emptyset$ can
be done analogously.

Third part of the proof. By Prop. A.1, to prove that $S_{\operatorname{M}}$
embeds $2L$ with embedding $\psi(y)=-L_{y}$, we only need to show that
$S_{\operatorname{M}}(-L_{y})=2L_{y}$. For every $z\in\mathcal{Y}$, we have

$\displaystyle S_{\operatorname{M}}(-L_{y},z)$
$\displaystyle=\max_{y^{\prime}\in\mathcal{Y}}~{}L(z,y^{\prime})+(-L_{y})^{\top}e_{y^{\prime}}-(-L_{y})^{\top}e_{z}$
$\displaystyle=\max_{y^{\prime}\in\mathcal{Y}}~{}\\{L(z,y^{\prime})-L(y,y^{\prime})\\}+L(y,z)$
$\displaystyle=2L(y,z),$

where at the last step we have used $L(z,y^{\prime})-L(y,y^{\prime})\leq
L(y,y^{\prime})$ as $L$ is a distance and so the maximization is achieved at
$y^{\prime}=y$.

Finally, the argmax decoding is consistent as it is an inverse of the
embedding $\psi(y)=-L_{y}$ as

$d(\psi(y))=\operatorname*{arg\;max}_{y^{\prime}\in\mathcal{Y}}~{}-L(y,y^{\prime})=\operatorname*{arg\;min}_{y^{\prime}\in\mathcal{Y}}~{}L(y,y^{\prime})=y.$

∎

###  B.4 Partial Consistency through dominant label condition

######  Lemma B.10.

Let $q\in\Delta$ such that $q_{1}\geq 1/2\geq p_{y}$ for all $y\neq 1$. If $L$
is a distance, then $L_{1}^{\top}q\leq L_{y}^{\top}q$ for all
$y\in\mathcal{Y}$.

###### Proof.

$\displaystyle L_{z}^{\top}q$ $\displaystyle=q_{1}L_{z1}+\sum_{y\neq
1,z}L_{zy}q_{y}$ $\displaystyle\geq\frac{1}{2}L_{z1}+\sum_{y\neq
1,z}L_{zy}q_{y}$ $\displaystyle=\Big{(}\frac{1}{2}-\sum_{y\neq
1,z}q_{y}\Big{)}L_{z1}+\sum_{y\neq 1,z}(L_{z1}+L_{zy})q_{y}$
$\displaystyle\geq\Big{(}\frac{1}{2}-\sum_{y\neq
1,z}q_{y}\Big{)}L_{z1}+\sum_{y\neq 1,z}L_{1y}q_{y}$ $\displaystyle\geq
L_{z1}q_{z}+\sum_{y\neq 1,z}L_{1y}q_{y}$ $\displaystyle=\sum_{y\neq
1}L_{1y}q_{y}=L_{1}^{\top}q.$

∎

######  Lemma B.11.

If $L$ is a distance, then $H_{\operatorname{M}}\leq 2H_{L}$.

###### Proof.

In particular, $L$ is also symmetric. Recall that

$\displaystyle H_{L}(q)$
$\displaystyle=\min_{y\in\mathcal{Y}}L_{y}^{\top}q=\min_{\begin{subarray}{c}a\succeq
Lp,\\\
p\in\Delta.\end{subarray}}~{}a^{\top}q=\min_{a\in\mathcal{P}_{L}}~{}a^{\top}q$
(23) $\displaystyle\frac{1}{2}H_{\operatorname{M}}(q)$
$\displaystyle=\min_{1a^{\top}+a1^{\top}\succeq
L}~{}a^{\top}q=\min_{a\in\mathcal{P}_{L}^{\operatorname{M}}}~{}a^{\top}q,$
(24)

where the second expression is given by Prop. A.3. To show that
$2H_{\operatorname{M}}\leq H_{L}$ we will show that
$\mathcal{P}_{L}\subseteq\mathcal{P}_{L}^{\operatorname{M}}$. If
$a\in\mathcal{P}_{L}$, then there exists $p\in\Delta$ such that $a\succeq Lp$.
Moreover, if $L$ is a distance, it means that the triangle inequality
$L(y,y^{\prime})\leq L(y,z)+L(z,y^{\prime})$, which is equivalent to $L\preceq
1L_{z}^{\top}+L_{z}1^{\top}$ for all $z\in\mathcal{Z}$. This can also be
written as

$L\preceq 1p^{\top}L+Lp1^{\top},\hskip 14.22636pt\forall p\in\Delta.$ (25)

Finally, note that if $Lp\preceq a$, then $Lp1^{\top}\preceq a1^{\top}$, and
the same holds for its transpose $1p^{\top}L\preceq 1a^{\top}$. Hence, we
obtain that $L\preceq 1a^{\top}+a1^{\top}$, which is equivalent to
$a\in\mathcal{P}_{L}^{\operatorname{M}}$. ∎

######  Proposition B.12.

If $L$ is a distance, then $\frac{1}{2}H_{\operatorname{M}}(q)=H_{L}(q)$, for
all $q\in\Delta$ such that $\|q\|_{\infty}\geq 1/2$. Moreover, under this
condition on $q$, it is calibrated with the argmax decoding.

###### Proof.

Combining Lemma B.10 and Lemma B.11 gives

$H_{\operatorname{M}}(q)\leq 2H_{L}(q)=2L_{y}^{\top}q,$

for all $q\in\Delta$ such that $p_{y}\geq 1/2\geq p_{z}$ for all $z\neq y$.
Hence, in order to prove the equality at these dominant label points, we just
need to find a matrix $Q\in U(q,q)$ such that $\langle
L,Q\rangle_{\operatorname{F}}=2L_{y}^{\top}q$. We define the matrix $Q$ as

$Q_{ij}=\left\\{\begin{array}[]{lr}q_{i}&\text{if }(i=y)\wedge(i\neq j)\\\
q_{j}&\text{if }(j=y)\wedge(j\neq i)\\\ 2q_{y}-1&\text{if }i=j=y\\\
0&\text{otherwise.}\end{array}\right..$

The matrix $Q$ has $q$ at the $y$-th row and $y$-th column and $2q_{y}-1$ at
the crossing point, instead of $2q_{y}$. The matrix is in $U(q,q)$ as the sum
of the rows and columns gives $q$ and it is non-negative because $2q_{y}-1\geq
0$ by assumption. Moreover, the objective satisfies

$\displaystyle\langle
L,Q\rangle_{\operatorname{F}}=\sum_{y\in\mathcal{Y}}~{}L_{y^{\prime}}^{\top}Q_{y^{\prime}}$
$\displaystyle=L_{y}^{\top}Q_{y}+\sum_{y^{\prime}\neq
y}L_{y^{\prime}}Q_{y^{\prime}}$
$\displaystyle=L_{y}^{\top}q+\sum_{y^{\prime}\neq
y}q_{y^{\prime}}L_{y^{\prime}}e_{y}$
$\displaystyle=L_{y}^{\top}q+\sum_{y^{\prime}\neq
y}q_{y^{\prime}}L(y,y^{\prime})=2L_{y}^{\top}q.$

The first part of the result follows. For the second part, we show that
$v_{\operatorname{M}}^{\star}(q)=-L_{y}$ at the points $q$ satisfying the
assumption. Note that we have
$H_{\operatorname{M}}(q)=2L_{y}^{\top}q=S(v^{\star}(q))^{\top}q$, so we only
need to show $S_{\operatorname{M}}(-L_{y})=2L_{y}$. For every
$z\in\mathcal{Y}$, we have

$\displaystyle S_{\operatorname{M}}(-L_{y},z)$
$\displaystyle=\max_{y^{\prime}\in\mathcal{Y}}~{}L(z,y^{\prime})+(-L_{y})^{\top}e_{y^{\prime}}-(-L_{y})^{\top}e_{z}$
$\displaystyle=\max_{y^{\prime}\in\mathcal{Y}}~{}\\{L(z,y^{\prime})-L(y,y^{\prime})\\}+L(y,z)$
$\displaystyle=2L(y,z),$

where at the last step we have used $L(z,y^{\prime})-L(y,y^{\prime})\leq
L(y,y^{\prime})$ as $L$ is a distance and so the maximization is achieved at
$y^{\prime}=y$. ∎

##  Appendix C PROOFS ON RESTRICTED-MAX-MARGIN LOSS

The following assumption A1 will be key to prove our consistency results.
Assumption A1: If $q$ is an extreme point of $\Delta(y^{\prime})$ for some
$y^{\prime}\in\mathcal{Y}$, then

$\\{q\in\Delta(y)\\}\vee\\{q_{y}=0\\},\hskip 14.22636pt\forall
y\in\mathcal{Y}.$ (26)

The following Lemma C.1 will be useful for the results below.

######  Lemma C.1.

If A1 is satisfied, then $\Delta(y)\cap\Delta(y^{\prime})\neq\emptyset$ for
all $y,y^{\prime}\in\mathcal{Y}$.

###### Proof.

If $\Delta(y)\cap\Delta(y^{\prime})=\emptyset$ and A1 is satisfied, then for
every $q$ extreme point of $\Delta(y^{\prime})$ we have that $q_{y}=0$. Hence,
the prediction set $\Delta(y)$ is included in the non full-dimensional
polyhedron $\Delta\cap\\{e_{y}=0\\}$. As
$\Delta=\cup_{y\in\mathcal{Y}}~{}\Delta(y)$, this implies that the point
$e_{y^{\prime}}\in\Delta(y^{\prime})$ must be necessarily included in another
$\Delta(z)$, which can only be possible if $L(z,y)=0$. However, by assumption
$L(z,y)=0$ if and only if $z=y$. ∎

The following Lemma C.2 shows that under A1, the Restricted-Max-Margin loss
embeds the loss $L$, which in turn implies consistency.

######  Lemma C.2.

Assume A1. If $q$ is an extreme point of $\Delta(y)$ for some
$y\in\mathcal{Y}$, then

$qq^{\top}\in\underset{Q\in
U(q,q)\cap\mathcal{C}_{L}}{\operatorname*{arg\;max}}\langle
L,Q\rangle_{\operatorname{F}}\hskip 14.22636pt\text{and}\hskip
14.22636pt\Omega_{\operatorname{MM}}(q)=\Omega_{\operatorname{RM}}(q).$

###### Proof.

The matrix $qq^{\top}$ belongs to $U(q,q)$ as $qq^{\top}1=q$ and
$qq^{\top}\succeq 0$ and to $\mathcal{C}_{L}$ by assumption. Let $z\in
y^{\star}(q)$. We have that

$\displaystyle-\Omega_{\operatorname{RM}}(q)$ $\displaystyle=\underset{Q\in
U(q,q)\cap\mathcal{C}_{L}}{\max}\langle L,Q\rangle_{\operatorname{F}}$
$\displaystyle\geq\langle
L,qq^{\top}\rangle_{\operatorname{F}}=\sum_{y}q_{y}L_{y}^{\top}q=\sum_{y}q_{y}L_{z}^{\top}q$
$\displaystyle=L_{z}^{\top}(1^{\top}qq^{\top})=L_{z}^{\top}q=-\Omega_{\operatorname{MM}}(q)$

We have shown that
$\Omega_{\operatorname{RM}}(q)\leq\Omega_{\operatorname{MM}}(q)$. Combining
with Proposition 3.4 that states
$\Omega_{\operatorname{RM}}\geq\Omega_{\operatorname{MM}}$, we obtain that
$\Omega_{\operatorname{RM}}(q)=\Omega_{\operatorname{MM}}(q)$. ∎

######  Theorem C.3.

If A1 is satisfied, the Restricted-Max-Margin loss embeds $L$ with embedding
$\psi(y)=-L_{y}$ and the loss is consistent to $L$ under the argmax decoding.

###### Proof.

We split the proof into two parts.

##### First part: $\boldsymbol{S_{\operatorname{RM}}}$ embeds
$\boldsymbol{L}$.

Let $z\in y^{\star}(q)$, so that $q\in\Delta(z)$. We can write $q$ as a convex
combination of extreme points of the polytope $\Delta(z)$ as

$q=\sum_{i=1}^{m}\alpha_{i}q_{i},$

where $\alpha\in\Delta_{m}$ and $q_{i}$ is an extreme point of $\Delta(z)$.
The matrix $Q=\sum_{i=1}^{m}\alpha_{i}q_{i}q_{i}^{\top}$ belongs to
$U(q,q)\cap\mathcal{C}_{L}$ as:

  * •

$Q\in U(q,q)$: We have
$Q1=\sum_{i=1}^{m}\alpha_{i}q_{i}q_{i}^{\top}1=\sum_{i=1}^{m}\alpha_{i}q_{i}=q$,
the same holds for $Q^{\top}$ and
$\sum_{i=1}^{m}\alpha_{i}q_{i}q_{i}^{\top}\succeq 0$.

  * •

$Q\in\mathcal{C}_{L}$: For all $y\in\mathcal{Y}$, we have
$(1L_{y}^{\top}-L)Q_{y}=\sum_{i=1}^{m}\alpha_{i}\underbrace{q_{i,y}(1L_{y}^{\top}-L)q_{i}}_{\preceq
0}\preceq 0$.

Moreover, we obtain:

$\displaystyle-\Omega_{\operatorname{RM}}(q)$ $\displaystyle=\underset{Q\in
U(q,q)\cap\mathcal{C}_{L}}{\max}\langle L,Q\rangle_{\operatorname{F}}$
$\displaystyle\geq\langle
L,Q\rangle_{\operatorname{F}}=\sum_{i=1}^{m}\alpha_{i}\langle
L,q_{i}q_{i}^{\top}\rangle_{\operatorname{F}}$
$\displaystyle=-\sum_{i=1}^{m}\alpha_{i}\Omega_{\operatorname{RM}}(q_{i})=-\sum_{i=1}^{m}\alpha_{i}\Omega_{\operatorname{MM}}(q_{i})$
$\displaystyle=\sum_{i=1}^{m}\alpha_{i}L_{z}^{\top}q_{i}=L_{z}^{\top}q=-\Omega_{\operatorname{MM}}(q)$

We have shown $\Omega_{\operatorname{RM}}\leq\Omega_{\operatorname{MM}}$.
Combining with Proposition 3.4 that states
$\Omega_{\operatorname{RM}}\geq\Omega_{\operatorname{MM}}$, we obtain
$\Omega_{\operatorname{RM}}=\Omega_{\operatorname{MM}}$.

##### Second part: the embedding is $\boldsymbol{\psi(y)=-L_{y}}$.

By Prop. A.1, we only need to show that $\psi(z)=-L_{z}$, i.e.,

$S_{\operatorname{RM}}(-L_{z},y)=\sup_{q\in\Delta(y)}~{}L_{y}^{\top}q+(-L_{z})^{\top}q-(-L_{z})^{\top}e_{y}=L(y,z),$

which holds whenever

$\max_{q\in\Delta(y)}~{}(L_{y}-L_{z})^{\top}q=0,$ (27)

for all $y,z\in\mathcal{Y}$. Note that by construction
$(L_{y}-L_{z})^{\top}q\leq 0$ for all $q\in\Delta(y)$. Moreover, by Lemma C.1
we have that $\Delta(z)\cap\Delta(y)\neq\emptyset$, so there exists
$q\in\Delta(y)$ with $L_{y}^{\top}q=L_{z}^{\top}q$.

Finally, the argmax decoding is consistent as it is an inverse of the
embedding $\psi(y)=-L_{y}$ as

$d(\psi(y))=\operatorname*{arg\;max}_{y^{\prime}\in\mathcal{Y}}~{}-L(y,y^{\prime})=\operatorname*{arg\;min}_{y^{\prime}\in\mathcal{Y}}~{}L(y,y^{\prime})=y.$

∎

######  Proposition C.4.

Assume that $q\in\Delta(y)\implies q_{y}>0$ for all $q\in\Delta$. Then A1 is
satisfied.

###### Proof.

We will prove that if the Assumption is not satisfied then it exists a vertex
of $\Delta(y)$ for some $y\in\mathcal{Y}$ such that $S\cap T\neq\emptyset$. If
the Assumption is not satisfied at vertex $q$, then
$\\{q\notin\Delta(y)\\}\wedge\\{q_{y}>0\\}$, which means in particular that
$S\cup T\subsetneq[k]$. This necessarily means that $S\cap T\neq\emptyset$
because we must have $|S|+|T|\geq k$ to have maximal rank as $q$ is a vertex.
∎

######  Proposition C.5.

Consistency of the Max-Margin implies consistency of Restricted-Max-Margin.

###### Proof.

From Prop. B.1 and Prop. B.5, we know that if the Max-Margin loss is
consistent to $L$, then the extreme points of the prediction sets
$\Delta(y)$’s have to be of the form $1/2(e_{y}+e_{y^{\prime}})$. We will see
that in this case (A1) is always satisfied. Indeed, if $q$ is an extreme point
of a prediction set, then is of the form $q=1/2(e_{y}+e_{y^{\prime}})$, which
satisfies $\\{q\in\Delta(z)\\}\vee\\{q_{z}=0\\}$ for all $z\in\mathcal{Y}$,
because $q\in\Delta(z)$ if $z\in\\{y,y^{\prime}\\}$ and $q_{z}=0$ otherwise. ∎