How does one show that the multi-class hinge loss upper bounds the 1-0 loss?

Question

I was trying to understand the mathematical claim that:

$$ \mathbb{1}\{ \hat y \neq y \} \leq \max_{j \in \{1,...,K \} } \left( \mathbb{1}\{ i \neq y\} + W^T_jx - W^T_y x \right) $$

I tried showing it was true but got stuck. The part I do understand is when $\hat y = y$. In that case its trivial to show the bound because one just notices that if $j=y$ then $\mathbb{1}\{ j \neq y\} + W^T_jx - W^T_y x = \mathbb{1}\{ y \neq y\} + W^T_yx - W^T_y x =0$. Since one of the terms in the maximaziation is zero then the other ones don't matter because if they are less than zero they won't be chosen (so they can't violate the inequality) but if they are larger than 0 then that great, they make the inequality "easier" to satisfy. There is a zero so the value must be at least 0 which shows its greater than the LHS.

But I have problems with $\hat y \neq y$. If $j=y$ we have zero again for the same reason as in the previous paragraph. But if $j \neq y$ then we have:

$$ \mathbb{1}\{ j \neq y\} + W^T_jx - W^T_y x = 1 + W^T_jx - W^T_y x $$

since $j \neq y$ then it means $W^T_jx - W^T_y x \neq 0$ (most likely not zero at least). However, my worry is that for all the remaining $j$'s (not equal to y) that they are negative enough to make the RHS less than 1 which makes the claimed inequality not hold. What is it about the problem that makes this impossible? I assume the inequality is correct since they are mentioned in university notes here.

Also, what I find extremely strange is that the right hand side is suppose to be a loss function but never does it seem to be a function of $\hat y$ (our prediction), at least not explicitly. Why is that? How would an ML algorithm be driven to improve $\hat y$ if it doesn't explicitly appear on the RHS? I assume it must implicitly appear or something of that sort so that we go minimize it, but its unclear to me.

---

Some progress? I noticed that since the RHS is a max and there is always a zero in the max (because of the case $j=y$) then if the max chooses a value such that $j \neq y$ then we have:

$$ 1 + W^T_j x - W^T_y x \geq 0 $$

which still doesn't guarantee its greater than 1 but at least its a new insight...

Answer 1

Using the notation $$L(j):=I(j\ne y) + (W^T_jx - W^T_yx),\tag1$$ the assertion is that $$I(\hat y \ne y) \le\max_{j\in\{1,\ldots,K\}} L(j).\tag2$$ You can prove this assertion in one go, without the need to consider cases, as follows. The RHS of (2) is at least as big as $L(\hat y)$, since $\hat y$ is one of the $j$'s. Plugging $j=\hat y$ into (1) yields $$ L(\hat y) := I(\hat y\ne y) + (W_{\hat y}^Tx - W^T_yx).\tag3 $$ But $W^T_{\hat y}x \ge W^T_yx$ since $\hat y$ by definition is the maximizer of $W^T_i$ over all $i$. Thus the parenthesized term in (3) is non-negative. Summarizing: $$ \max_{j\in\{1,\ldots,K\}} L(j)\ge L(\hat y)\ge I(\hat y\ne y). $$