Confused about The Realizability Assumption

Question

From the book "Understanding Machine Learning: From Theory to Algorithms", The Realizability Assumption is defined as follows:

There exists $h^{\star}\in \mathcal{H}$ s.t. $L_{(D,f)}(h^{\star})=0$. Note that this assumption implies that with probability 1 over random samples, $S$, where the instances of $S$ are are sampled according to $\mathcal{D}$ and labeled by $f$, we have $L_{S}(h^{\star})=0$. The realizability assumption implies that for every ERM hypothesis we have that $L_{S}(h_S)=0$. However, we are interested in the true risk of $h_S$, $L_{(D,f)}(h_S)$, rather than its empirical risk.

Isn't the true risk $\big{(} L_{(D,f)}(h_S) \big{)}$ already ZERO by the definition of the realizability assumption?, I mean isn't $L_{S}(h_S)=0$ because $L_{(D,f)}(h_S)=0$? and if it isn't, why then the realizability assumption implies that $L_{S}(h_S)=0$?

Answer 1

$L_{(\mathcal{D}, f)}(h)$ for any $h$ represents the population risk of the given $h \in \mathcal{H}$.

The realizability assumption states that there exists some $h^*$ such that it minimizes population risk, however it is now upto the learning algorithm (popularly ERM) to find $h^*$.

The next uncertainty is that ERM only has a sample of our population ($S_n \sim \mathcal{D}^n$) to find $h^*$. The best it can do is minimize $L_{S_n}(h)$, which is empirical risk. This gives us our "best-guess" hypothesis $h_S$.

We want $h_S = h^*$, in which case our problem is solved, however this is not guaranteed - therefore, we use the PAC learning paradigm, which in the realizable setting finds $h_{S_n}$ within some generalization bound $\varepsilon$ with probability $1-\delta$.

Since $S_n \subset \mathcal{D},\ L_s \subset L_{(\mathcal{D}, f)}$. If $L_S(h) \neq 0$, we know for certain that $L_{(\mathcal{D}, f)}(h) \neq 0$. However, if $L_S(h) = 0$, it could be that $L_{(\mathcal{D}, f)}(h) \neq 0$, which is likely to happen if $h_{S_n}$ overfits to the training dataset. Conversely, if $L_{(\mathcal{D}, f)}(h) = 0$, we know $L_S(h) = 0$.