Convex Margin-Based Loss Functions

• Definition: Given a measurable prediction function $f : X \rightarrow Y$, a measurable loss function $\ell : Y \times Y \rightarrow \mathbb{R}<em>[InvisibleComma]+$, and a probability distribution $P(X,Y)$ on $X \times Y$, the expected risk of $f$ is defined as $R</em>\ell(f) := E[\ell(f(X), Y)] = \int[InvisibleComma]{X \times Y} \ell(f(x), y) P(X,Y) {dx, dy}$

• Definition: The Bayes (optimal) risk $R<em>\ell^{\star}$ is given by $R</em>\ell^{\star} = \inf { R_\ell(f) | f \text{ is measurable } }$. A function $f^{\star} : X \rightarrow Y$ that attains the above infimum is called Bayes predictor or Bayes (optimal) learning rule.

• Proposition: A Bayes optimal learning rule satisfies for $P_X$-almost all $x \in X$

  $f^{\star}(x) \in \operatorname{argmin}<em>{y' \in Y} E[ \ell(y', Y) | X = x ] = \operatorname{argmin}</em>{y' \in Y} r(y' | x)$

Examples: Bayes Risk and Bayes Predictor

• Example: Binary Classification

  • $Y = {-1, 1}$, $\ell(z, y) = 1_{z \neq y}$.

  • The risk can be decomposed as follows:

    $R_\ell(f) = E[\ell(f(X), Y)] = P{f(X) \neq Y}$

    $= E[1<em>{f(X)=1}P{Y = -1 | X} + 1</em>{f(X)=-1}P{Y = 1 | X}]$

  • From this, we derive the (optimal) Bayes classifier for $P_X$-almost all $x$:

    $f^{\star}(x) = \begin{cases} -1, &amp; \text{if } P<em>{Y|X=x}{-1} &gt; P</em>{Y|X=x}{1} \ 1, &amp; \text{otherwise} \end{cases}$

    • However, this leads to combinatorial optimization problems, which can be computationally intractable (NP-hard).

    • Can we define convex loss functions for real-valued prediction function that achieve the Bayes optimal risk?

Convex margin-based loss functions

Problem: Different loss functions lead to different optimal functions.

Question: Let $g^{\star} : X \rightarrow \mathbb{R}$ be the function that minimizes the $\Phi$-risk $R_\Phi$

$R_\Phi(g) := E[\Phi(Y g(X))]$,

where $\Phi$ is a convex margin-based loss function (surrogate of the 0-1-loss).

Does $\operatorname{sign}(g^{\star})$ agree with the Bayes classifier $f^{\star}$?

Convex margin-based loss functions (II)

• Definition: A margin-based loss (measurable) function $\Phi : \mathbb{R} \rightarrow \mathbb{R}$ is classification calibrated if $\operatorname{sign}(g^{\star}) = f^{\star}$, where $g^{\star}$ minimizes $R_\Phi$ and $f^{\star}$ is a Bayes classifier.

Convex margin-based loss functions

• Theorem: Let $\Phi$ be a margin-based, convex loss function. Then $\Phi$ is classification calibrated if and only if $\Phi$ is differentiable at 0 and \Phi'(0) < 0.
  
  

  Examples:

  Loss Function	Formula
  Exponential Loss	${ \Phi(z) = e^{-z} }$
  Hinge Loss	${ \Phi(z) = \max(0, 1 - z) }$
  Truncated Squared Loss	${ \Phi(z) = \begin{cases} (1 - z)^2, & z < 1 \ 0, & z \geq 1 \end{cases} }$
  Squared Loss	${ \Phi(z) = (1 - z)^2 }$
  Logistic Loss	${ \Phi(z) = \ln(1 + e^{-z}) }$

Convex margin-based loss functions (II)

• Derivation of the theorem: The $\Phi$-risk can be decomposed as follows (set $\eta(x) := P_{Y|X=x}{1}$)

  $R_\Phi(g) := E[\Phi(Y g(X))] = E[ E[\Phi(Y g(X)) | X] ]$

  $= E[\Phi(-g(X)) P{Y = -1 | X} + \Phi(g(X)) P{Y = 1 | X}]$

  $= E[\eta(X) \Phi(g(X)) + (1 - \eta(X)) \Phi(-g(X))]$.

Convex margin-based loss functions (III)

Introduce conditional $\Phi$-risk given $\eta(x) =: \xi \in [0, 1]$:

${ r_\Phi(z | \xi) := \xi \Phi(z) + (1 - \xi) \Phi(-z) }$

Convex margin-based loss functions (IV)

Therefore, we have ${ R<em>\Phi(g) = E[r</em>\Phi(g(X) | \eta(X))] }$.

Convex margin-based loss functions (V)

Since we optimize over all measurable functions ${ g : X \rightarrow \mathbb{R} }$, the problem reduces to pointwise minimization { P_X-almost everywhere.

Convex margin-based loss functions (VI)

Therefore, consider minimization of ${ r_\Phi(z | \xi) }$ for given ${ \xi \in [0, 1] }$ (corresponds to ${ \eta(x) }$).

Convex margin-based loss functions (VII)

We remark that ${ \Phi }$ is classification calibrated if the following equivalences hold true

{ 2\xi - 1 > 0 \quad \iff \quad \operatorname{argmin}z r\Phi(z | \xi) \in (0, \infty) } and { 2\xi - 1 < 0 \quad \iff \quad \operatorname{argmin}z r\Phi(z | \xi) \in (-\infty, 0) }.

Convex margin-based loss functions (VIII)

Since ${ \Phi }$ is convex, also ${ r<em>\Phi(z | \xi) }$ is convex in ${ z }$. We abbreviate ${ \tilde{c}</em>\xi(z) := r_\Phi(z | \xi) }$.

Convex margin-based loss functions (IX)

Use monotonicity of the directional derivatives ${ \tilde{c}'_\xi(\cdot; +1) }$ to obtain

{ \tilde{c}'\xi(0; +1) = \xi \Phi'(0; +1) + (1 - \xi) \Phi'(0; -1) < 0 \quad \iff \quad \operatorname{argmin}z \tilde{c}_\xi(z) \in (0, \infty) }.

Analogously, { \tilde{c}'\xi(0; +1) > 0 } if and only if ${ \operatorname{argmin}</em>z \tilde{c}_\xi(z) \in (-\infty, 0) }$.

Convex margin-based loss functions (X)

Therefore, consider minimization of ${ r_\Phi(z | \xi) }$ for given ${ \xi \in [0, 1] }$ (corresponds to ${ \eta(x) }$).

We remark that ${ \Phi }$ is classification calibrated if the following equivalences hold true

{ 2\xi - 1 > 0 \quad \iff \quad \operatorname{argmin}z r\Phi(z | \xi) \in (0, \infty) } and { 2\xi - 1 < 0 \quad \iff \quad \operatorname{argmin}z r\Phi(z | \xi) \in (-\infty, 0) }.

Since ${ \Phi }$ is convex, also ${ r<em>\Phi(z | \xi) }$ is convex in ${ z }$. We abbreviate ${ \tilde{c}</em>\xi(z) := r_\Phi(z | \xi) }$.

Use monotonicity of the directional derivatives ${ \tilde{c}'_\xi(\cdot; +1) }$ to obtain

{ \tilde{c}'\xi(0; +1) = \xi \Phi'(0; +1) + (1 - \xi) \Phi'(0; -1) < 0 \quad \iff \quad \operatorname{argmin}z \tilde{c}_\xi(z) \in (0, \infty) }.

Analogously, { \tilde{c}'\xi(0; +1) > 0 } if and only if ${ \operatorname{argmin}</em>z \tilde{c}_\xi(z) \in (-\infty, 0) }$.

Convex margin-based loss functions (XI)

${ \implies }$

${ \impliedby }$

Convex margin-based loss functions (XII)

"$\implies$"

Now, assume ${ \Phi }$ is classification calibrated. Let ${ \xi \searrow \frac{1}{2} }$ to observe that

${ \tilde{c}'_\xi(0; +1) = \frac{1}{2} (\Phi'(0; +1) - \Phi'(0; -1)) \leq 0 }$.

Moreover, by monotonicity of the (directional) derivatives, we always have ${ \Phi'(0; -1) \leq \Phi(0; +1) }$, which yields ${ \Phi'(0; -1) = \Phi'(0; +1) }$ and hence ${ \Phi }$ is differentiable at 0. We conclude that ${ \tilde{c}'<em>\xi(0) = (2\xi - 1) \Phi'(0) }$. Using { \xi > \frac{1}{2} }, yields ${ \operatorname{argmin}</em>z \tilde{c}<em>\xi(z) \in (0, \infty) }$, which induces that { \tilde{c}'\xi(0) < 0 }, and we deduce that { \Phi'(0) < 0 }.