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.