Learning Classifiers with Fenchel-Young Losses: Generalized Entropies, Margins, and Algorithms

Introduction

Loss functions are a cornerstone of statistics and machine learning: They measure the difference, or “loss,” between a ground-truth label and a prediction. Some loss functions, such as the hinge loss of support vector machines, are intimately connected to the notion of separation margin—a prevalent concept in statistical learning theory, which has been used to prove the famous perceptron mistake bound (Rosenblatt, 1958) and many other generalization bounds (Vapnik, 1998; Schölkopf and Smola, 2002). For probabilistic classification, the most popular loss is arguably the (multinomial) logistic loss. It is smooth, enabling fast convergence rates, and the softmax operator provides a consistent mapping to probability distributions. However, the logistic loss does not enjoy a margin, and the generated probability distributions have dense support, which is undesirable in some applications for interpretability or computational efficiency reasons.

To address these shortcomings, Martins and Astudillo (2016) proposed a new loss based on the projection onto the simplex. Unlike the logistic loss, this “sparsemax” loss has a natural separation margin and induces a sparse probability distribution. However, the sparsemax loss was derived in a relatively ad-hoc manner and it is still relatively poorly understood. Thorough understanding of the core principles underpinning these losses, enabling the creation of new losses combining their strengths, is still lacking.

This paper studies and extends Fenchel-Young (F-Y) losses, recently proposed for structured prediction (Niculae et al., 2018). We show that F-Y losses provide a generic and principled way to construct a loss with an associated probability distribution. We uncover a fundamental connection between generalized entropies, margins, and sparse probability distributions. In sum, we make the following contributions.

We introduce regularized prediction functions to generalize the softmax and sparsemax transformations, possibly beyond the probability simplex (§2).

We study F-Y losses and their properties, showing that they unify many existing losses, including the hinge, logistic, and sparsemax losses (§3).

We then show how to seamlessly create entire new families of losses from generalized entropies. We derive efficient algorithms to compute the associated probability distributions, making such losses appealing both in theory and in practice (§4).

We characterize which entropies yield sparse distributions and losses with a separation margin, notions we prove to be intimately connected (§5).

Finally, we demonstrate F-Y losses on the task of sparse label proportion estimation (§6).

Regularized prediction functions

We emphasize that the regularization is w.r.t. the output and not w.r.t. the model parameters $W$, as is usually the case in the literature. The optimization problem in (1) balances between two terms: an “affinity” term ${\langle\bm{\theta},{\bm{p}}\rangle}$, and a “confidence” term $\Omega({\bm{p}})$ which should be low if ${\bm{p}}$ is “uncertain”. Two important classes of convex $\Omega$ are (squared) norms and, when $\operatorname*{\mathsf{dom}}(\Omega)$ is the probability simplex, generalized negative entropies. However, our framework does not require $\Omega$ to be convex in general. Allowing extended-real $\Omega$ further permits general domain constraints in (1) via indicator functions, as we now illustrate.

When $\Omega=I_{\triangle^{d}}$, $\widehat{{\bm{y}}}_{\Omega}(\bm{\theta})$ is a one-hot representation of the argmax prediction

We can see that output as a probability distribution that assigns all probability mass on the same class. When $\Omega=-\mathsf{H}^{\textsc{s}}+I_{\triangle^{d}}$, where $\mathsf{H}^{\textsc{s}}({\bm{p}})\coloneqq-\sum_{i}p_{i}\log p_{i}$ is Shannon’s entropy, $\widehat{{\bm{y}}}_{\Omega}(\bm{\theta})$ is the well-known softmax

See Boyd and Vandenberghe (2004, Ex. 3.25) for a derivation. The resulting distribution always has dense support. When $\Omega=\frac{1}{2}\|\cdot\|^{2}+I_{\triangle^{d}}$, $\widehat{{\bm{y}}}_{\Omega}$ is the Euclidean projection onto the probability simplex

a.k.a. the sparsemax transformation (Martins and Astudillo, 2016). The distribution has sparse support (it may assign exactly zero probability to low-scoring classes) and can be computed exactly in $O(d)$ time (Brucker, 1984; Duchi et al., 2008; Condat, 2016). This paradigm is not limited to the probability simplex: When $\Omega({\bm{p}})=-\sum_{i}\mathsf{H}^{\textsc{s}}([p_{i},1-p_{i}])+I_{^{d}}({\bm{p}})$, we get

i.e., the sigmoid function evaluated coordinate-wise. We can think of its output as a positive measure (unnormalized probability distribution).

We now discuss simple properties of regularized prediction functions. The first two assume that $\Omega$ is a symmetric function, i.e., that it satisfies

where $\mathcal{P}$ is the set of $d\times d$ permutation matrices.

Properties of $\widehat{{\bm{y}}}_{\Omega}(\bm{\theta})$

Effect of a permutation. If $\Omega$ is symmetric, then $\forall\bm{P}\in\mathcal{P}$: $\widehat{{\bm{y}}}_{\Omega}(\bm{P}\bm{\theta})=\bm{P}\widehat{{\bm{y}}}_{\Omega}(\bm{\theta})$.

Order preservation. Let ${\bm{p}}=\widehat{{\bm{y}}}_{\Omega}(\bm{\theta})$. If $\Omega$ is symmetric, then the coordinates of ${\bm{p}}$ and $\bm{\theta}$ are sorted the same way, i.e., $\theta_{i}>\theta_{j}\Rightarrow p_{i}\geq p_{j}$ and $p_{i}>p_{j}\Rightarrow\theta_{i}>\theta_{j}$.

Gradient mapping. $\widehat{{\bm{y}}}_{\Omega}(\bm{\theta})$ is a subgradient of $\Omega^{*}$ at $\bm{\theta}$, i.e., $\widehat{{\bm{y}}}_{\Omega}(\bm{\theta})\in\partial\Omega^{*}(\bm{\theta})$. If $\Omega$ is strictly convex, $\widehat{{\bm{y}}}_{\Omega}(\bm{\theta})$ is the gradient of $\Omega^{*}$, i.e., $\widehat{{\bm{y}}}_{\Omega}(\bm{\theta})=\nabla\Omega^{*}(\bm{\theta})$.

Temperature scaling. For any constant $t>0$, $\widehat{{\bm{y}}}_{t\Omega}(\bm{\theta})\in\partial\Omega^{*}(\nicefrac{{\bm{\theta}}}{{t}})$. If $\Omega$ is strictly convex, $\widehat{{\bm{y}}}_{t\Omega}(\bm{\theta})=\widehat{{\bm{y}}}_{\Omega}(\nicefrac{{\bm{\theta}}}{{t}})=\nabla\Omega^{*}(\nicefrac{{\bm{\theta}}}{{t}})$.

The proof is given in §C.1. For classification, the order-preservation property ensures that the highest-scoring class according to $\bm{\theta}$ and $\widehat{{\bm{y}}}_{\Omega}(\bm{\theta})$ agree with each other:

Temperature scaling is useful to control how close we are to unregularized prediction functions.

Fenchel-Young losses

In this section, we introduce Fenchel-Young losses as a natural way to learn models whose output layer is a regularized prediction function. {definition}Fenchel-Young loss generated by $\Omega$

Fenchel-Young losses can also be written as $L_{\Omega}(\bm{\theta};{\bm{y}})=f_{\bm{\theta}}({\bm{y}})-f_{\bm{\theta}}(\widehat{{\bm{y}}}_{\Omega}(\bm{\theta}))$, where $f_{\bm{\theta}}({\bm{p}})\coloneqq\Omega({\bm{p}})-{\langle\bm{\theta},{\bm{p}}\rangle}$, highlighting the relation with the regularized prediction function $\widehat{{\bm{y}}}_{\Omega}(\bm{\theta})$. Therefore, as long as we can compute $\widehat{{\bm{y}}}_{\Omega}(\bm{\theta})$, we can evaluate the associated Fenchel-Young loss $L_{\Omega}(\bm{\theta};{\bm{y}})$. Examples of Fenchel-Young losses are given in Table 1. In addition to the aforementioned multinomial logistic and sparsemax losses, we recover the squared, hinge and one-vs-all logistic losses, for suitable choices of $\Omega$ and $\operatorname*{\mathsf{dom}}(\Omega)$.

As the name indicates, this family of loss functions is grounded in the Fenchel-Young inequality (Borwein and Lewis, 2010, Proposition 3.3.4)

The inequality, together with well-known properties of convex conjugates, imply the following results. {proposition}Properties of F-Y losses

Zero loss. If $\Omega$ is a lower semi-continuous proper convex function, then $\min_{\bm{\theta}}L_{\Omega}(\bm{\theta};{\bm{y}})=0$ and $L_{\Omega}(\bm{\theta};{\bm{y}})=0$ iff ${\bm{y}}\in\partial\Omega^{*}(\bm{\theta})$. If $\Omega$ is strictly convex, then $L_{\Omega}(\bm{\theta};{\bm{y}})=0$ iff ${\bm{y}}=\widehat{{\bm{y}}}_{\Omega}(\bm{\theta})=\nabla\Omega^{*}(\bm{\theta})$.

Convexity & subgradients. $L_{\Omega}$ is convex in $\bm{\theta}$ and the residual vectors are its subgradients: $\widehat{{\bm{y}}}_{\Omega}(\bm{\theta})-{\bm{y}}\in\partial L_{\Omega}(\bm{\theta};{\bm{y}})$.

Differentiability & smoothness. If $\Omega$ is strictly convex, then $L_{\Omega}$ is differentiable and $\nabla L_{\Omega}(\bm{\theta};{\bm{y}})=\widehat{{\bm{y}}}_{\Omega}(\bm{\theta})-{\bm{y}}$. If $\Omega$ is strongly convex, then $L_{\Omega}$ is smooth, i.e., $\nabla L_{\Omega}(\bm{\theta};{\bm{y}})$ is Lipschitz continuous.

Temperature scaling. For any constant $t>0$, $L_{t\Omega}(\bm{\theta};{\bm{y}})=tL_{\Omega}(\nicefrac{{\bm{\theta}}}{{t}};{\bm{y}})$.

Remarkably, the non-negativity and convexity properties hold even if $\Omega$ is not convex. The zero loss property follows from the fact that, if $\Omega$ is l.s.c. proper convex, then (9) becomes an equality (i.e., the duality gap is zero) if and only if $\bm{\theta}\in\partial\Omega({\bm{p}})$. It suggests that minimizing a Fenchel-Young loss requires adjusting $\bm{\theta}$ to produce predictions $\widehat{{\bm{y}}}_{\Omega}(\bm{\theta})$ that are close to the target ${\bm{y}}$, reducing the duality gap.

with equality when the loss is . If ${\mathcal{C}}=\operatorname*{\mathsf{dom}}(\Psi)$, i.e., $\Omega=\Psi$, then $L_{\Omega}(\bm{\theta};{\bm{y}})=B_{\Omega}({\bm{y}}||\widehat{{\bm{y}}}_{\Omega}(\bm{\theta}))$. As an example, applying (11) with $\Psi=\frac{1}{2}\|\cdot\|^{2}$ and ${\mathcal{C}}=\triangle^{d}$, we get that the sparsemax loss is a convex upper-bound for the non-convex $\frac{1}{2}\|{\bm{y}}-\operatorname*{\mathsf{sparsemax}}(\cdot)\|^{2}$. This suggests that the sparsemax loss can be useful for sparse label proportion estimation, as we confirm in §6.

New loss functions for sparse probabilistic classification

In the previous section, we presented Fenchel-Young losses in a broad setting. We now restrict to classification over the probability simplex and show how to easily create several entire new families of losses.

A natural choice of regularization function $\Omega$ over the probability simplex is $\Omega=-\mathsf{H}$, where $\mathsf{H}$ is a generalized entropy (DeGroot, 1962; Grünwald and Dawid, 2004): a concave function over $\triangle^{d}$, used to measure the “uncertainty” in a distribution ${\bm{p}}\in\triangle^{d}$.

Assumptions: We will make the following assumptions about $\mathsf{H}$.

Zero entropy: $\mathsf{H}({\bm{p}})=0$ if ${\bm{p}}$ is a delta distribution, i.e., ${\bm{p}}\in\{\bm{e}_{i}\}_{i=1}^{d}$.

Strict concavity: \mathsf{H}\big{(}(1-\alpha){\bm{p}}+\alpha{\bm{p}}^{\prime}\big{)}>{(1-\alpha)}\mathsf{H}({\bm{p}})+\alpha\mathsf{H}({\bm{p}}^{\prime}), for ${\bm{p}}\neq{\bm{p}}^{\prime}$, $\alpha\in(0,1)$.

Symmetry: $\mathsf{H}({\bm{p}})=\mathsf{H}(\bm{P}{\bm{p}})$ for any $\bm{P}\in\mathcal{P}$.

If the ground truth is ${\bm{y}}=\bm{e}_{k}$ and assumption A.1. holds, (8) becomes

This expression shows that Fenchel-Young losses over $\triangle^{d}$ can be written solely in terms of the generalized “cumulant function” $(-\mathsf{H})^{*}$. Indeed, when $\mathsf{H}$ is Shannon’s entropy, we recover the cumulant (a.k.a. log-partition) function $(-\mathsf{H}^{\textsc{s}})^{*}(\bm{\theta})=\log\sum_{i=1}^{d}\exp(\theta_{i})$. When $\mathsf{H}$ is strongly concave over $\triangle^{d}$, we can also see $(-\mathsf{H})^{*}$ as a smoothed max operator (Niculae and Blondel, 2017; Mensch and Blondel, 2018) and hence $L_{-\mathsf{H}}(\bm{\theta};\bm{e}_{k})$ can be seen as a smoothed upper-bound of the perceptron loss $(\bm{\theta};\bm{e}_{k})\mapsto\max_{i\in[d]}\theta_{i}-\theta_{k}$.

We now give two examples of generalized entropies. The resulting families of prediction and loss functions, new to our knowledge, are illustrated in Figure 1. We provide more examples in §A.

Defined as \mathsf{H}^{\textsc{t}}_{\alpha}({\bm{p}})\coloneqq k(\alpha-1)^{-1}\big{(}1-\|\cdot\|^{\alpha}_{\alpha}\big{)}, where $\alpha\geq 1$ and $k$ is an arbitrary positive constant, these entropies arise as a generalization of the Shannon-Khinchin axioms to non-extensive systems (Suyari, 2004) and have numerous scientific applications (Gell-Mann and Tsallis, 2004; Martins et al., 2009). For convenience, we set $k=\alpha^{-1}$ for the rest of this paper. Tsallis entropies satisfy assumptions A.1–A.3 and can also be written in uniformly separable form:

The limit case $\alpha\rightarrow 1$ corresponds to the Shannon entropy. When $\alpha=2$, we recover the Gini index (Gini, 1912), a popular “impurity measure” for decision trees:

It is easy to check that $L_{-\mathsf{H}^{\textsc{t}}_{2}}$ recovers the sparsemax loss (Martins and Astudillo, 2016) (cf. Table 1). Another interesting case is $\alpha\rightarrow+\infty$, which gives $\mathsf{H}^{\textsc{t}}_{\infty}({\bm{p}})=0$, hence $L_{-\mathsf{H}^{\textsc{t}}_{\infty}}$ is the perceptron loss in Table 1. The resulting “$\operatorname*{\mathsf{argmax}}$” distribution puts all probability mass on the top-scoring classes. In summary, $\widehat{{\bm{y}}}_{-\mathsf{H}^{\textsc{t}}_{\alpha}}$ for $\alpha\in\{1,2,\infty\}$ is $\operatorname*{\mathsf{softmax}}$, $\operatorname*{\mathsf{sparsemax}}$, and $\operatorname*{\mathsf{argmax}}$, and $L_{-\mathsf{H}^{\textsc{t}}_{\alpha}}$ is the logistic, sparsemax and perceptron loss, respectively. Tsallis entropies induce a continuous parametric family subsuming these important cases. Since the best surrogate loss often depends on the data (Nock and Nielsen, 2009), tuning $\alpha$ typically improves accuracy, as we confirm in §6.

An interesting class of non-separable entropies are entropies generated by a $q$-norm, defined as $\mathsf{H}^{\textsc{n}}_{q}({\bm{p}})\coloneqq 1-\|{\bm{p}}\|_{q}$. We call them norm entropies. From the Minkowski inequality, $q$-norms with $q>1$ are strictly convex on the simplex, so $\mathsf{H}^{\textsc{n}}_{q}$ satisfies assumptions A.1–A.3 for $q>1$. The limit case $q\rightarrow\infty$ is particularly interesting: in this case, we obtain $\mathsf{H}^{\textsc{n}}_{\infty}=1-\|\cdot\|_{\infty}$, recovering the Berger-Parker dominance index (Berger and Parker, 1970), widely used in ecology to measure species diversity. We surprisingly encounter $\mathsf{H}^{\textsc{n}}_{\infty}$ again in §5, as a limit case for the existence of separation margins.

For non-separable entropies $\mathsf{H}$, the regularized prediction function $\widehat{{\bm{y}}}_{-\mathsf{H}}(\bm{\theta})$ does not generally enjoy a closed-form expression and one must resort to projected gradient methods to compute it. Fortunately, for uniformly separable entropies, which we saw to be the case of Tsallis entropies, we now show that $\widehat{{\bm{y}}}_{-\mathsf{H}}(\bm{\theta})$ can be computed in linear time. {proposition}Reduction to root finding

where $\tau$ is a root of $\phi(t)\coloneqq{\langle{\bm{p}}(t),\bm{1}\rangle}-1$, in the tight search interval $[\tau_{\min},\tau_{\max}]$, where $\tau_{\min}\coloneqq\max(\bm{\theta})+h^{\prime}(1)$ and $\tau_{\max}\coloneqq\max(\bm{\theta})+h^{\prime}\left(\nicefrac{{1}}{{d}}\right)$. An approximate $\tau$ such that $|\phi(\tau)|\leq\epsilon$ can be found in $O(\nicefrac{{1}}{{\log\epsilon}})$ time by, e.g., bisection. The related problem of Bregman projection onto the probability simplex was recently studied by Krichene et al. (2015) but our derivation is different and more direct (cf. §C.4).

Separation margin of F-Y losses

In this section, we are going to see that the simple assumptions A.1–A.3 about a generalized entropy $\mathsf{H}$ are enough to obtain results about the separation margin associated with $L_{-\mathsf{H}}$. The notion of margin is well-known in machine learning, lying at the heart of support vector machines and leading to generalization error bounds (Vapnik, 1998; Schölkopf and Smola, 2002; Guermeur, 2007). We provide a definition and will see that many other Fenchel-Young losses also have a “margin,” for suitable conditions on $\mathsf{H}$. Then, we take a step further, and connect the existence of a margin with the sparsity of the regularized prediction function, providing necessary and sufficient conditions for Fenchel-Young losses to have a margin. Finally, we show how this margin can be computed analytically. {definition}Separation margin

The most famous example of a loss with a separation margin is the multi-class hinge loss, $L(\bm{\theta};\bm{e}_{k})=\max\{0,\max_{j\neq k}1+\theta_{j}-\theta_{k}\}$, which we saw in Table 1 to be a Fenchel-Young loss: it is immediate from the definition that its margin is $1$. Less trivially, Martins and Astudillo (2016, Prop. 3.5) showed that the sparsemax loss also has the separation margin property. On the negative side, the logistic loss does not have a margin, as it is strictly positive. Characterizing which Fenchel-Young losses have a margin is an open question which we address next.

The loss $L_{-\mathsf{H}}$ has a separation margin iff there is a $m>0$ such that $m\bm{e}_{k}\in\partial(-\mathsf{H})(\bm{e}_{k})$.

If the above holds, then the margin of $L_{-\mathsf{H}}$ is given by the smallest such $m$ or, equivalently,

Reassuringly, the first part confirms that the logistic loss does not have a margin, since $\partial(-\mathsf{H}^{\textsc{s}})(\bm{e}_{k})=\varnothing$. A second interesting fact is that the denominator of (18) is the generalized entropy $\mathsf{H}^{\textsc{n}}_{\infty}({\bm{p}})$ introduced in §4: the $\infty$-norm entropy. As Figure 1 suggests, this entropy provides an upper bound for convex losses with unit margin. This provides some intuition to the formula (18), which seeks a distribution ${\bm{p}}$ maximizing the entropy ratio between $\mathsf{H}({\bm{p}})$ and $\mathsf{H}^{\textsc{n}}_{\infty}({\bm{p}})$.

The next result, proved in §C.6, characterizes more precisely the image of $\nabla(-\mathsf{H})^{*}$. In doing so, it establishes a key result in this paper: a sufficient condition for the existence of a separation margin in $L_{-\mathsf{H}}$ is the sparsity of the regularized prediction function $\widehat{{\bm{y}}}_{-\mathsf{H}}\equiv\nabla(-\mathsf{H})^{*}$, i.e., its ability to reach the entire simplex, including the boundary points. If $\mathsf{H}$ is uniformly separable, this is also a necessary condition. {proposition}Equivalence between sparse probability distribution and loss enjoying a margin

Let $\mathsf{H}$ satisfy A.1–A.3 and be uniformly separable, i.e., $\mathsf{H}({\bm{p}})=\sum_{i=1}^{d}h(p_{i})$. Then the following statements are all equivalent:

$\partial(-\mathsf{H})({\bm{p}})\neq\varnothing$ for any ${\bm{p}}\in\triangle^{d}$;

$L_{-\mathsf{H}}$ has the separation margin property.

For a general $\mathsf{H}$ (not necessarily separable) satisfying A.1–A.3, we have (1) $\Leftrightarrow$ (2) $\Rightarrow$ (3).

Let us reflect for a moment on the three conditions stated in Proposition 5. The first two conditions involve the subdifferential and gradient of $-\mathsf{H}$ and its conjugate; the third condition is the margin property of $L_{-\mathsf{H}}$. To provide some intuition, consider the case where $\mathsf{H}$ is separable with $\mathsf{H}({\bm{p}})=\sum_{i}h(p_{i})$ and $h$ is differentiable in $(0,1)$. Then, from the concavity of $h$, its derivative $h^{\prime}$ is decreasing, hence the first condition is met if $\lim_{t=0^{+}}h^{\prime}(t)<\infty$ and $\lim_{t=1^{-}}h^{\prime}(t)>-\infty$. This is the case with Tsallis entropies for $\alpha>1$, but not Shannon entropy, since $h^{\prime}(t)=-1-\log t$ explodes at . Functions whose gradient “explodes” in the boundary of their domain (hence failing to meet the first condition in Proposition 5) are called “essentially smooth” (Rockafellar, 1970). For those functions, $\nabla(-\mathsf{H})^{*}$ maps only to the relative interior of $\triangle^{d}$, never attaining boundary points (Wainwright and Jordan, 2008); this is expressed in the second condition. This prevents essentially smooth functions from generating a sparse ${\bm{y}}_{-\mathsf{H}}\equiv\nabla(-\mathsf{H})^{*}$ or (if they are separable) a loss $L_{-\mathsf{H}}$ with a margin, as asserted by the third condition. Since Legendre-type functions (§3) are strictly convex and essentially smooth, by Proposition 3, loss functions for which the composite form $L_{-\mathsf{H}}(\bm{\theta};{\bm{y}})=B_{-\mathsf{H}}({\bm{y}}||\widehat{{\bm{y}}}_{-\mathsf{H}}(\bm{\theta}))$ holds, which is the case of the logistic loss but not of the sparsemax loss, do not enjoy a margin and cannot induce a sparse probability distribution. This is geometrically visible in Figure 1.

For Fenchel-Young losses that have the separation margin property, Proposition 5 provided a formula for determining the margin. While informative, formula (18) is not very practical, as it involves a generally non-convex optimization problem. The next proposition, proved in §C.7, takes a step further and provides a remarkably simple closed-form expression for generalized entropies that are twice-differentiable. To simplify notation, we denote by $\nabla_{j}\mathsf{H}({\bm{p}})\equiv(\nabla\mathsf{H}({\bm{p}}))_{j}$ the $j^{\text{th}}$ component of $\nabla\mathsf{H}({\bm{p}})$. {proposition} Assume $\mathsf{H}$ satisfies the conditions in Proposition 5 and is twice-differentiable on the simplex. Then, for arbitrary $j\neq k$:

The compact formula (19) provides a geometric characterization of separable entropies and their margins: (20) tells us that only the slopes of $h$ at the two extremities of $$ are relevant in determining the margin.

As seen in §4, Tsallis entropies are separable with $h(t)=(t-t^{\alpha})/(\alpha(\alpha-1))$. For $\alpha>1$, $h^{\prime}(t)=(1-\alpha t^{\alpha-1})/(\alpha(\alpha-1))$, hence $h^{\prime}(0)=1/(\alpha(\alpha-1))$ and $h^{\prime}(1)=-1/\alpha$. Proposition 5 then yields

Norm entropies, while not separable, have gradient $\nabla\mathsf{H}^{\textsc{n}}_{q}({\bm{p}})=-(\nicefrac{{{\bm{p}}}}{{\|{\bm{p}}\|_{q}}})^{q-1}$, giving $\nabla\mathsf{H}^{\textsc{n}}_{q}(\bm{e}_{k})=-\bm{e}_{k}$, so

as confirmed visually in Figure 1, in the binary case.

Experimental results

As we saw, $\alpha$-Tsallis entropies generate a family of losses, with the logistic ($\alpha\to 1$) and sparsemax losses ($\alpha=2$) as important special cases. In addition, they are twice differentiable for $\alpha\in[1,2)$, produce sparse probability distributions for $\alpha>1$ and are computationally efficient for any $\alpha\geq 1$, thanks to Proposition 4. In this section, we demonstrate their usefulness on the task of label proportion estimation and compare different solvers for computing $\widehat{{\bm{y}}}_{-\mathsf{H}^{\textsc{t}}_{\alpha}}$.

We use L-BFGS (Liu and Nocedal, 1989) for simplicity. From Proposition 9 and using the chain rule, we obtain the gradient expression $\nabla R(W)=(\widehat{Y}_{\Omega}-Y)^{\top}X+\lambda W$, where $\widehat{Y}_{\Omega}$, $Y$ and $X$ are matrices whose rows gather $\widehat{{\bm{y}}}_{\Omega}(W{\bm{x}}_{i})$, ${\bm{y}}_{i}$ and ${\bm{x}}_{i}$, for $i=1,\dots,n$. At test time, we predict label proportions by ${\bm{p}}={\bm{y}}_{-\mathsf{H}^{\textsc{t}}_{\alpha}}(W{\bm{x}})$.

We ran experiments on $7$ standard multi-label benchmark datasets — see §B for dataset characteristics. For all datasets, we removed samples with no label, normalized samples to have zero mean unit variance, and normalized labels to lie in the probability simplex. We chose $\lambda\in\{10^{-4},10^{-3},\dots,10^{4}\}$ and $\alpha\in\{1,1.1,\dots,2\}$ against the validation set. We report the test set mean Jensen-Shannon divergence, $\text{JS}({\bm{p}},{\bm{y}})\coloneqq\frac{1}{2}\text{KL}({\bm{p}}||\frac{{\bm{p}}+{\bm{y}}}{2})+\frac{1}{2}\text{KL}({\bm{y}}||\frac{{\bm{p}}+{\bm{y}}}{2})$, and the mean squared error $\frac{1}{2}\|{\bm{p}}-{\bm{y}}\|^{2}$ in Table 3. As can be seen, the loss with tuned $\alpha$ achieves the best averaged rank overall. Tuning $\alpha$ allows to choose the best loss in the family in a data-driven fashion. Additional experiments confirm these findings — see §B.

Related work

recovering the well-known relation between Bregman divergences and proper scoring rules. For example, using the Gini index $\mathsf{H}({\bm{p}})=1-\|{\bm{p}}\|^{2}$ generates the Brier score (Brier, 1950) $S_{-\mathsf{H}}({\bm{p}};\bm{e}_{k})=\sum_{i=1}^{d}([[k=i]]-p_{i})^{2}$, showing that the sparsemax loss and the Brier score share the same generating function. More generally, while a scoring rule $S_{\Omega}$ is related to a primal-space Bregman divergence, a Fenchel-Young loss $L_{\Omega}$ can be seen as a mixed-space Bregman divergence (§3). This difference has a number of important consequences. First, $S_{\Omega}$ is not necessarily convex in ${\bm{p}}$ (Williamson et al. (2016, Proposition 17) show that it is in fact quasi-convex). In contrast, $L_{\Omega}$ is always convex in $\bm{\theta}$. Second, the first argument is constrained to $\triangle^{d}$ for $S_{\Omega}$, while unconstrained for $L_{\Omega}$.

Thus, in this case, Fenchel-Young losses and proper composite losses coincide up to the constant term $\Omega({\bm{y}})$ (which vanishes if ${\bm{y}}=\bm{e}_{k}$ and $\Omega$ satisfies assumption A.1), with $\bm{\psi}^{-1}=\widehat{{\bm{y}}}_{\Omega}$ the canonical inverse link function. Fenchel-Young losses, however, require neither invertible link nor Legendre type assumptions, allowing to express losses (e.g., hinge or sparsemax) that are not expressible in composite form. Moreover, as seen in §5, a Legendre-type $\Omega$ precisely precludes sparse probability distributions and losses enjoying a margin.

Nock and Nielsen (2009) proposed binary classification losses based on the Legendre transformation but require invertible mappings. Masnadi-Shirazi (2011) studied the Bayes consistency of related binary classification loss functions. Duchi et al. (2018, Proposition 3) derived the multi-class loss (12), a special case of Fenchel-Young loss over the probability simplex, and showed (Proposition 4) that any strictly concave generalized entropy generates a classification-calibrated loss. Amid and Warmuth (2017) proposed a different family of losses based on the Tsallis divergence, to interpolate between convex and non-convex losses, for robustness to label noise.

Fenchel duality also plays a key role in smoothing techniques (Nesterov, 2005; Beck and Teboulle, 2012), which have been used extensively to create smoothed losses (Shalev-Shwartz and Zhang, 2016). However, these techniques were applied on a per-loss basis and were not connected to the induced probability distribution. In contrast, we propose a generic construction, with clear links between smoothing and the distribution induced by $\widehat{{\bm{y}}}_{\Omega}$.

Conclusion

We showed that regularization and Fenchel duality provide simple core principles, unifying many existing loss functions, and allowing to create useful new ones easily. In particular, we derived a new family of loss functions based on Tsallis entropies, which includes the logistic, sparsemax and perceptron losses as special cases. With the unique exception of the logistic loss, losses in this family induce sparse probability distributions. We also showed a close and fundamental relationship between generalized entropies, losses enjoying a margin and sparse probability distributions. Remarkably, Fenchel-Young losses can be defined over arbitrary domains, allowing to construct loss functions for a large variety of applications (Blondel et al., 2019).

MB thanks Arthur Mensch and Gabriel Peyré for numerous fruitful discussions and Tim Vieira for introducing him to generalized exponential families. AM and VN were partially supported by the European Research Council (ERC StG DeepSPIN 758969) and by the Fundação para a Ciência e Tecnologia through contracts UID/EEA/50008/2013 and CMUPERI/TIC/0046/2014 (GoLocal).

References

Appendix A More examples of generalized entropies

In this section, we give two more examples of generalized entropies: squared norm entropies and Rényi entropies.

Inspired by Niculae and Blondel (2017), as a simple extension of the Gini index (15), we consider the following generalized entropy based on squared $q$-norms:

The constant term $\frac{1}{2}$, omitted by Niculae and Blondel (2017), ensures satisfaction of A.1. For $q\in(1,2]$, it is known that the squared $q$-norm is strongly convex w.r.t. $\|\cdot\|_{q}$ (Ball et al., 1994), implying that $(-\mathsf{H}^{\textsc{sq}}_{q})^{*}$, and therefore $L_{-\mathsf{H}^{\textsc{sq}}_{q}}$, is smooth. Although $\widehat{{\bm{y}}}_{-\mathsf{H}^{\textsc{sq}}_{q}}(\bm{\theta})$ cannot be solved in closed form for $q\in(1,2)$, it can be solved efficiently using projected gradient descent methods.

Rényi entropies (Rényi, 1961) are defined for any $\beta\geq 0$ as:

Unlike Shannon and Tsallis entropies, Rényi entropies are not separable, with the exception of $\beta\rightarrow 1$, which also recovers Shannon entropy as a limit case. The case $\beta\rightarrow+\infty$ gives $\mathsf{H}^{\textsc{r}}_{\beta}({\bm{p}})=-\log\|{\bm{p}}\|_{\infty}$. For $\beta\in$, Rényi entropies satisfy assumptions A.1–A.3; for $\beta>1$, Rényi entropies fail to be concave. They are however pseudo-concave (Mangasarian, 1965), meaning that, for all ${\bm{p}},\bm{q}\in\triangle^{d}$, ${\langle\nabla\mathsf{H}^{\textsc{r}}_{\beta}({\bm{p}}),\bm{q}-{\bm{p}}\rangle}\leq 0$ implies $\mathsf{H}^{\textsc{r}}_{\beta}(\bm{q})\leq\mathsf{H}^{\textsc{r}}_{\beta}({\bm{p}})$. This implies, among other things, that points ${\bm{p}}\in\triangle^{d}$ with zero gradient are maximizers of ${\langle{\bm{p}},\bm{\theta}\rangle}+\mathsf{H}^{\textsc{r}}_{\beta}({\bm{p}})$, which allows us to compute the predictive distribution $\widehat{{\bm{y}}}_{-\mathsf{H}^{\textsc{r}}_{\beta}}$ with gradient-based methods.

Appendix B Experiment details and additional empirical results

The datasets we used in §6 are summarized below.

The datasets can be downloaded from http://mulan.sourceforge.net/datasets-mlc.html and https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/.

Appendix C Proofs

In this section, we give proofs omitted from the main text.

Let $\Omega$ be symmetric. We first prove that $\Omega^{*}$ is symmetric as well. Indeed, we have

The last equality was obtained by a change of variable ${\bm{p}}^{\prime}=\bm{P}^{\top}{\bm{p}}$, from which ${\bm{p}}$ is recovered as ${\bm{p}}=\bm{P}{\bm{p}}^{\prime}$, which proves $\nabla\Omega^{*}(\bm{P}{\bm{p}})=\bm{P}\nabla\Omega^{*}({\bm{p}})$.

Since $\Omega^{*}$ is convex, the gradient operator $\nabla\Omega^{*}$ is monotone, i.e.,

which implies $\theta_{i}>\theta_{j}\Rightarrow p_{i}\geq p_{j}$ and $p_{i}>p_{j}\Rightarrow\theta_{i}\geq\theta_{j}$. To fully prove the claim, we need to show that the last inequality is strict: to do this, we simply invoke $\nabla\Omega^{*}(\bm{P}{\bm{p}})=\bm{P}\nabla\Omega^{*}({\bm{p}})$ with a matrix $\bm{P}$ that permutes $i$ and $j$, from which we must have $\theta_{i}=\theta_{j}\Rightarrow p_{i}=p_{j}$.

This follows directly from Danskin’s theorem (Danskin, 1966). See also Bertsekas (1999, Proposition B.25).

This immediately follows from properties of the $\operatorname*{\mathsf{argmax}}$ operator.

C.2 Proof of Proposition 3

We set $\Omega\coloneqq\Psi+I_{\mathcal{C}}$.

The last two terms are independent of ${\bm{p}}$ and therefore

where ${\mathcal{C}}\subseteq\operatorname*{\mathsf{dom}}(\Psi)$. The r.h.s. is the Bregman projection of $\nabla\Psi^{*}(\bm{\theta})=\widehat{{\bm{y}}}_{\Psi}(\bm{\theta})$ onto ${\mathcal{C}}$.

Let ${\bm{p}}=\widehat{{\bm{y}}}_{\Omega}(\bm{\theta})$. Using (31), we obtain

where we assumed ${\bm{y}}\in{\mathcal{C}}$ and ${\mathcal{C}}\subseteq\operatorname*{\mathsf{dom}}(\Psi)$, implying $\Psi({\bm{y}})=\Omega({\bm{y}})$.

If ${\mathcal{C}}=\operatorname*{\mathsf{dom}}(\Psi)$ (i.e., $\Omega=\Psi$), then ${\bm{p}}=\nabla\Psi^{*}(\bm{\theta})$ and $B_{\Psi}({\bm{p}}||\nabla\Psi^{*}(\bm{\theta}))=0$. We thus get the composite form of Fenchel-Young losses

Let ${\bm{p}}=\widehat{{\bm{y}}}_{\Omega}(\bm{\theta})$. Since ${\bm{p}}$ is the Bregman projection of $\nabla\Psi^{*}(\bm{\theta})$ onto ${\mathcal{C}}$, we can use the well-known Pythagorean theorem for Bregman divergences (see, e.g., Banerjee et al. (2005, Appendix A)) to obtain for all ${\bm{y}}\in{\mathcal{C}}\subseteq\operatorname*{\mathsf{dom}}(\Psi)$:

Using (35), we obtain for all ${\bm{y}}\in{\mathcal{C}}\subseteq\operatorname*{\mathsf{dom}}(\Psi)$:

Since $\Omega$ is a l.s.c. proper convex function, from Proposition 9, we immediately get

C.3 Proof of Proposition 4

The two facts stated in Proposition 4 ($\mathsf{H}$ is always non-negative and maximized by the uniform distribution) follow directly from Jensen’s inequality. Indeed, for all ${\bm{p}}\in\triangle^{d}$:

$\mathsf{H}({\bm{p}})\geq\sum_{j=1}^{d}p_{j}\mathsf{H}(\bm{e}_{j})=0$;

$\mathsf{H}(\mathbf{1}/d)=\mathsf{H}\left(\sum_{\bm{P}\in\mathcal{P}}\frac{1}{d!}\bm{P}{\bm{p}}\right)\geq\sum_{\bm{P}\in\mathcal{P}}\frac{1}{d!}\mathsf{H}(\bm{P}{\bm{p}})=\mathsf{H}({\bm{p}})$,

where $\mathcal{P}$ is the set of $d\times d$ permutation matrices. Strict concavity ensures that ${\bm{p}}=\bm{1}/d$ is the unique maximizer.

C.4 Proof of Proposition 4

From strict convexity and the definition of the convex conjugate,

The constrained optimization problem above has Lagrangian

A solution $({\bm{p}}^{\star},\bm{\nu}^{\star},\tau^{\star})$ must satisfy the KKT conditions

Since $g$ is strictly convex, $g^{\prime}$ is increasing and so $\tau_{\min}<\tau_{\max}$. For any $\tau\in[\tau_{\min},\tau_{\max}]$, we construct $\bm{\nu}$ as

By construction, $\nu_{j}\geq 0$, satisfying dual feasability. Injecting $\nu$ into (42) and combining the two cases, we obtain

We show that i) the stationarity conditions have a unique solution given $\tau$, and ii) $[\tau_{\min},\tau_{\max}]$ forms a sign-changing bracketing interval, and thus contains $\tau^{\star}$, which can then be found by one-dimensional search. The solution verifies all KKT conditions, thus is globally optimal.

Since $g$ is strictly convex, its derivative $g^{\prime}$ is continuous and strictly increasing, and is thus a one-to-one mapping between $$and$[g^{\prime}(0),g^{\prime}(1)]$. Denote by$(g^{\prime})^{-1}\colon[g^{\prime}(0),g^{\prime}(1)]\rightarrow$its inverse. If$\theta_{j}-\tau\geq g^{\prime}(0)$, we have

Otherwise, $g^{\prime}(p_{j})=g^{\prime}(0)$. This verifies that the r.h.s. of (45) is always within the domain of $(g^{\prime})^{-1}$. We can thus apply the inverse to both sides to solve for $p_{j}$, obtaining

Strict convexity implies the optimal ${\bm{p}}^{\star}$ is unique; it can be seen that $\tau^{\star}$ is also unique. Indeed, assume optimal $\tau^{\star}_{1},\tau^{\star}_{2}$. Then, ${\bm{p}}(\tau^{\star}_{1})={\bm{p}}(\tau^{\star}_{2})$, so $\max(\bm{\theta}-\tau^{\star}_{1},g^{\prime}(0))=\max(\bm{\theta}-\tau^{\star}_{2},g^{\prime}(0))$. This implies either $\tau^{\star}_{1}=\tau^{\star}_{2}$, or $\bm{\theta}-\tau^{\star}_{\{1,2\}}\leq g^{\prime}(0)$, in which case ${\bm{p}}=\bm{0}\notin\triangle^{d}$, which is a contradiction.

Consider the primal infeasability function $\phi(\tau)\coloneqq{\langle{\bm{p}}(\tau),\bm{1}\rangle}-1$; ${\bm{p}}(\tau)$ is primal feasible iff $\phi(\tau)=0.$ We show that $\phi$ is decreasing on $[\tau_{\min},\tau_{\max}]$, and that it has opposite signs at the two extremities. From the intermediate value theorem, the unique root $\tau^{\star}$ must satisfy $\tau^{\star}\in[\tau_{\min},\tau_{\max}]$.

Since $g^{\prime}$ is increasing, so is $(g^{\prime})^{-1}$. Therefore, for all $j$, $p_{j}(\tau)$ is decreasing, and so is the sum $\phi(\tau)=\sum_{j}p_{j}(\tau)-1$. It remains to check the signs at the boundaries.

where we upper-bounded each term of the sum by the largest one. At the other end,

using that a sum of non-negative terms is no less than its largest term. Therefore, $\phi(\tau_{\min})\geq 0$ and $\phi(\tau_{\max})\leq 0$. This implies that there must exist $\tau^{\star}$ in $[\tau_{\min},\tau_{\max}]$ satisfying $\phi(\tau^{\star})=0$. The corresponding triplet $\left({\bm{p}}(\tau^{\star}),\bm{\nu}(\tau^{\star}),\tau^{\star}\right)$ thus satisfies all of the KKT conditions, confirming that it is the global solution.

Algorithm 1 is an example of a bisection algorithm for finding an approximate solution; more advanced root finding methods can also be used. We note that the resulting algorithm resembles the method provided in Krichene et al. (2015), with a non-trivial difference being the order of the thresholding and $(-g)^{-1}$ in Eq. (47).

C.5 Proof of Proposition 5

We start by proving the following lemma. {lemma} Let $\mathsf{H}$ satisfy assumptions A.1–A.3. Then:

We have $\bm{\theta}\in\partial(-\mathsf{H})(\bm{e}_{k})$ iff $\theta_{k}=(-\mathsf{H})^{*}(\bm{\theta})$. That is:

If $\bm{\theta}\in\partial(-\mathsf{H})(\bm{e}_{k})$, then, we also have $\bm{\theta}^{\prime}\in\partial(-\mathsf{H})(\bm{e}_{k})$ for any $\bm{\theta}^{\prime}$ such that $\theta_{k}^{\prime}=\theta_{k}$ and $\theta_{i}^{\prime}\leq\theta_{i}$, for all $i\neq k$.

Let $\Omega=-\mathsf{H}$. From Proposition 2 (order preservation), we can consider $\partial\Omega(\bm{e}_{1})$ without loss of generality, in which case any $\bm{\theta}\in\partial\Omega(\bm{e}_{1})$ satisfies $\theta_{1}=\max_{j}\theta_{j}$. We have $\bm{\theta}\in\partial\Omega(\bm{e}_{1})$ iff $\Omega(\bm{e}_{1})={\langle\bm{\theta},\bm{e}_{1}\rangle}-\Omega^{*}(\bm{\theta})=\theta_{1}-\Omega^{*}(\bm{\theta})$. Since $\Omega(\bm{e}_{1})=0$, we must have $\theta_{1}=\Omega^{*}(\bm{\theta})\geq\sup_{{\bm{p}}\in\triangle^{d}}{\langle\bm{\theta},{\bm{p}}\rangle}-\Omega({\bm{p}})$, which proves part 1. To see 2, note that we have $\theta_{k}^{\prime}=\theta_{k}\geq{\langle\bm{\theta},{\bm{p}}\rangle}-\Omega({\bm{p}})\geq{\langle\bm{\theta}^{\prime},{\bm{p}}\rangle}-\Omega({\bm{p}})$, for all ${\bm{p}}\in\triangle^{d}$, from which the result follows. $\blacksquare$

We now proceed to the proof of Proposition 5. Let $\Omega=-\mathsf{H}$, and suppose that $L_{\Omega}$ has the separation margin property. Then, $\bm{\theta}=m\bm{e}_{1}$ satisfies the margin condition $\theta_{1}\geq m+\max_{j\neq 1}\theta_{j}$, hence $L_{\Omega}(m\bm{e}_{1},\bm{e}_{1})=0$. From the first part of Proposition 9, this implies $m\bm{e}_{1}\in\partial\Omega(\bm{e}_{1})$.

Conversely, let us assume that $m\bm{e}_{1}\in\partial\Omega(\bm{e}_{1})$. From the second part of Lemma C.5, this implies that $\bm{\theta}\in\partial\Omega(\bm{e}_{1})$ for any $\bm{\theta}$ such that $\theta_{1}=m$ and $\theta_{i}\leq 0$ for all $i\geq 2$; and more generally we have $\bm{\theta}+c\mathbf{1}\in\partial\Omega(\bm{e}_{1})$. That is, any $\bm{\theta}$ with $\theta_{1}\geq m+\max_{i\neq 1}\theta_{i}$ satisfies $\bm{\theta}\in\partial\Omega(\bm{e}_{1})$. From Proposition 9, this is equivalent to $L_{\Omega}(\bm{\theta};\bm{e}_{1})=0$.

Let us now determine the margin of $L_{\Omega}$, i.e., the smallest $m$ such that $m\bm{e}_{1}\in\partial\Omega(\bm{e}_{1})$. From Lemma C.5, this is equivalent to $m\geq mp_{1}-\Omega({\bm{p}})$ for any ${\bm{p}}\in\triangle^{d}$, i.e., ${-\Omega({\bm{p}})}{(1-p_{1})}\leq m$. Note that by Proposition 2 the “most competitive” ${\bm{p}}$’s are sorted as $\bm{e}_{1}$, so we may write $p_{1}=\|{\bm{p}}\|_{\infty}$ without loss of generality. The margin of $L_{\Omega}$ is the smallest possible such margin, given by (18).

C.6 Proof of Proposition 5

Furthermore, since $m$ upper bounds the separation margin of $\mathsf{H}$, we have from Proposition 5 that $m\geq\frac{\mathsf{H}([1-p_{i}^{\prime},p_{i}^{\prime},0,\ldots,0])}{1-\max\{1-p_{i}^{\prime},p_{i}^{\prime}\}}=\frac{h(1-p_{i}^{\prime})+h(p_{i}^{\prime})}{\min\{p_{i}^{\prime},1-p_{i}^{\prime}\}}\geq\frac{h(p_{i}^{\prime})}{p_{i}^{\prime}}$ for any $p_{i}^{\prime}\in]0,1]$. Hence, we have

Summing all inequalities in Eqs. (57)–(58), we obtain the expression in Eq. (56), which finishes the proof.

C.7 Proof of Proposition 5

Define $\Omega=-\mathsf{H}$. Let us start by writing the margin expression (18) as a unidimensional optimization problem. This is done by noticing that the max-generalized entropy problem constrained to $\max({\bm{p}})=1-t$ gives ${\bm{p}}=\left[1-t,\frac{t}{d-1},\ldots,\frac{t}{d-1}\right]$, for $t\in\left[0,1-\frac{1}{d}\right]$ by a similar argument as the one used in Proposition 4. We obtain:

We write the argument above as $A(t)=\frac{-\Omega(\bm{e}_{1}+t\bm{v})}{t}$, where $\bm{v}:=[-1,\frac{1}{d-1},\ldots,\frac{1}{d-1}]$. We will first prove that $A$ is decreasing in $[0,1-\frac{1}{d}]$, which implies that the supremum (and the margin) equals $A(0)$. Note that we have the following expression for the derivative of any function $f(\bm{e}_{1}+t\bm{v})$:

Using this fact, we can write the derivative $A^{\prime}(t)$ as:

In turn, the derivative $B^{\prime}(t)$ is:

where we denote by $\nabla\nabla\Omega$ the Hessian of $\Omega$, and used the fact that it is positive semi-definite, due to the convexity of $\Omega$. This implies that $B$ is decreasing, hence for any $t\in$, $B(t)\leq B(0)=\Omega(\bm{e}_{1})=0$, where we used the fact $\|\nabla\Omega(\bm{e}_{1})\|<\infty$, assumed as a condition of Proposition 5. Therefore, we must also have $A^{\prime}(t)=\frac{B(t)}{t^{2}}\leq 0$ for any $t\in$, hence $A$ is decreasing, and $\sup_{t\in[0,1-1/d]}A(t)=\lim_{t\rightarrow 0+}A(t)$. By L’Hôpital’s rule: