How does the realizability assumption imply that there is always a hypothesis that gets zero train error?

Question

I was reading Shai-Shawrts and Shai Ben-David's Understanding Machine Learning book and it said after defintion 2.1 something like this:

The realizability assumption (i.e. that $E_{p_{x,y}} [loss(h^*(x),y)] = L_{(D,f)} (h^*) = 0 $ zero generalization error is achievable) implies that for every ERM hypothesis $h_S$ we have that $\frac{1}{N}\sum_i ZeroOneLoss(h_S(x_i),y_i) = 0$.

Why is this formally true? I was trying to show a proof but wasn't successful...I guess intuitively it seems plausible since if one can divide the data with some hyperplane (assume binary), it doesn't matter which hyperplane one chooses we can divide the data with any hyperplane as long as the data comes from something linearly separable. However, I didn't know how to translate this into something formal (though I tried). Any ideas?

---

Informally the proof is as follows:

Let $S_N$ denote the numbers of samples. Let $S_{\infty}$ be the full distribution "as data points". Note $h^*$ $L_{S_{\infty}}(h^*) = 0$ since its realizable. Notice that since $S_N \subset S_{\infty}$ it means that $L_{S_N}(h^*) = 0 $ for all $N$ including infinity. This is true because $h^*$ classifies points correctly always if we consider all the points from the data set so a subset of them must also be correct. If the hypothesis space contains $h^*$ then it must mean that ERM learning rule must select at least $h^*$ since $h^* \in \mathcal H$. Thus, $L_{S_N}(h_S) = 0 $ since $h^*$ achieves zero training error and its in the set of hypothesis its considering.

Answer 1

Informally the proof is as follows:

Let $S_N$ denote the numbers of samples. Let $S_{\infty}$ be the full distribution "as data points" (the part of the answer that requires more formalization). Note $h^*$ $L_{S_{\infty}}(h^*) = 0$ since its realizable. Notice that since $S_N \subset S_{\infty}$ it means that $L_{S_N}(h^*) = 0 $ for all $N$ including infinity. This is true because $h^*$ classifies points correctly always if we consider all the points from the data set so a subset of them must also be correct. If the hypothesis space contains $h^*$ then it must mean that ERM learning rule must select at least $h^*$ since $h^* \in \mathcal H$. Thus, $L_{S_N}(h_S) = 0 $ since $h^*$ achieves zero training error and its in the set of hypothesis its considering.

This is as rigorous as I can make it but improved answers would be appreciated!

Answer 2

In the case where the output is one-dimensional and continuous, I think the statement assumes that the model can be described as $f(x):\bigcup\left(\mathbb{R}^n, \mathbb{I}^m\right) \to \mathbb{R}$, where at least some of the inputs are continuous and the output is a smooth and continuous function that spans $\mathbb{R}$. If this is true, then for every possible set of observed input-output data, there is a set of inputs $x_i$ to the model that produces outputs that perfectly agree with the observed data, $f(x_i)$. In the extreme case where the input of $f$ is purely discrete and the output space is continuous, $f:\mathbb{I}^n \to \mathbb{R}$, it's not clear to me that the theorem would hold. It seems unlikely that $f$ would be continuous in $\mathbb{R}$, I think there would be gaps in the $f(x)$ space, so it is not clear that I would always be able to perfectly match each observed data point.