Confused about the realizability assumption and equations of upper bound I'm reading the the first chapter of Understanding machine learning from theory to algorithms and they said that:

Let $H_B$ be the set of "bad" hypotheses, that is

$H_B=\left\{h \in H:L_{(D,f)(h)}\gt e\right\}$ ($e$ is the accuracy parameter)

Let 

$M=\left\{S|_x : \exists \ h \in H_B, L_s(h) =0 \right\}$

be the set of misleading samples: Namely, for every $S|_x \in M$, there is a "bad" hypothesis, $h \in H_B$, that looks like a "good" hypothesis on $S|_x$. Now, recall that we would like to bound the probability of the event $L_{(D,f)} \gt e$. But, since
  the realizability assumption implies that $L_s(h_s)=0$, it follows that the event
  $L_{(D,f)}(h_s)\gt e$ can only happen if for some $h \in H_B$ we have $L_s(h) = 0$. In other words, this event will only happen if our sample is in the set of misleading samples $M$.
  Formally, we have shown that

$\left\{S|_x : L_{(D,f)}(h_S)\gt e \subseteq M\right\}$



I'm so confused about this conclusion. Can someone please explain this to me? Thanks for your time!
 A: Let's formulate the problem in a clearer way.
ASSUMPTIONS:


*

*$h_s = \underset{h\in\mathcal{H}}{\arg\min} \, L_{S}(h) \qquad$ (definition of ERM)

*$\exists h^{*} \in \mathcal{H}: L_{(\mathcal{D}, f)}(h^{*}) = 0 \qquad$ (realizability assumption)

*$\mathcal{H}_B = \{ h \in \mathcal{H}: L_{(\mathcal{D}, f)}(h) > \epsilon \}$

*$M = \{ S\vert_x: \exists h\in \mathcal{H}_{B}, \, L_{S}(h) = 0 \}$
PROVE: $\{S\vert_x: L_{(\mathcal{D}, f)}\left(h_{S} \right) > \epsilon \} \subseteq M$
PROOF:
To prove a set A is a subset of set B, or $A \subseteq B$, we need to prove that every element in set A is in set B. Here, given the definition of $\mathcal{H}_{B}$, we can rewrite set M as
$M = \{ S\vert_{x}: h \in \mathcal{H}, \, L_{(\mathcal{D}, f)}(h) > \epsilon, \, L_{S}(h) = 0 \}$.
Thus, to be an element in set $M$, it needs to satisfy the 3 conditions specified in set M.
Every element of the set on the right-hand side already satisfies two conditions:


*

*$h_{S} \in \mathcal{H}$

*$L_{(\mathcal{D}, f)}\left(h_{S} \right) > \epsilon$.


Hence, proving $L_{S}(h_{S}) = 0$ would complete the proof. This can be done by employing the definition of ERM and the realizability assumption.
From the realizability assumption combined with the fact that $S$ is a sample from $\mathcal{D}$:
$L_{(\mathcal{D}, f)}(h^{*}) = 0 \implies L_{S}(h^{*}) = 0$.
From the definition of ERM:
$L_{S}(h_S) \le L_{S}(h^{*}) = 0 \quad \implies L_{S}(h_S) = 0$.
A: I actually got stuck on this for a bit too ... 
Remember how $h_S$ is defined:
$$h_S \in \underset{h\in H}{\mathrm{argmin}} (L_S(h))$$
The realizability assumption will tell you there's a perfect $h^*$. (Very strong assumption). This $h^*$ will have $L_S(h^*)=0$ by definition. 
So when $h_S$ is defined as the argmin - it is necessarily 0 with probability 1. (This is not the same as the Loss function achieving 0 on every sample). 


*

*So we are looking for a class of predictors $h_S$

*The realizability assumption tells us that $L_S(h^*)=0$

*if $\exists h \in H_B$ s.t. $L_S(h)=0$, this implies that $h \in argmin$
The rest follows that the set we want to define is contained in $M$. I don't think this isn't a constructive proof - it doesn't tell you how to find a $h$, it ultimately shows that there's an upper bound on the size of the samples that would create the conditions to create a bad predictor. They don't really talk about measurability but there was a footnote suppressing those details and $H$ was finite, so I'm assuming everything works !
