In section 5.2 error decomposition (p.404) from the online book "Shai et al., Understanding Machine Learning: From Theory to Applications", the authors wrote:
As we have shown, for a finite hypothesis class, $\epsilon_{est}$ increases (logarithmically) with $|\mathcal{H}|$ and decreases with $m$.
Where $\epsilon_{est}$ denotes the estimation error, $\mathcal{H}$ is the hypothesis class and $m$ is the size of the training set.
However, I think that the authors had implicitly incorporated some sort of probability in that statement which I couldn't figure out. The reason is because, without probability, I can construct some counterexample for that the statement is not true. For example, let's consider the PAC learnable hypothesis class $\mathcal{H}_1$ and $\mathcal{H}_2$ such that $\mathcal{H}_1\subset\mathcal{H}_2$, a learning algorithm $A$ that implements ERM rule, a training sample $S$ of size $m$ sampled i.i.d according to some distribution $\mathcal{D}$. Denote by $h_{bayes}$ the target hypothesis in both $\mathcal{H}_1$ and $\mathcal{H}_2$, $A_{\mathcal{H}}$ the algorithm $A$ restricted to some $\mathcal{H}$ then we have that
$$ \epsilon_{est_1}:=L_\mathcal{D}(A_{\mathcal{H}_1}(S))-L_D(h_{bayes}) = L_\mathcal{D}(A_{\mathcal{H}_1}(S)),\\ \epsilon_{est}:=L_\mathcal{D}(A_{\mathcal{H}_2}(S))-L_D(h_{bayes_2}) = L_\mathcal{D}(A_{\mathcal{H}_2}(S)) $$
Now consider a slightly modified axis-aligned rectangle classification problem (mentioned in Exercise 2.3 in the book) with realizability assumption held. Let $h1_{(a_1,b_1,a_2,b_2)}$ and $h2_{(a_1,b_1,a_2,b_2)}$ be binary classifiers for points in the $xy$-plane to $\lbrace 0, 1\rbrace$ (where $a_1, a_2, b_1, b_2\in\mathbb{R}$, $a_1\le b_1$ and $a_2\le b_2$) such that:
$$ h1_{(a_1,b_1,a_2,b_2)}(x, y)= \begin{cases} 1\text{ if } x\in[a_1, b_1], y\in[a_2, b_2]\\ 0\text{ otherwise}, \end{cases} $$
and
$$ h2_{(a_1,b_1,a_2,b_2)}(x, y)= \begin{cases} 1\text{ if } x\notin[a_1, b_1], y\notin[a_2, b_2]\\ 0\text{ otherwise}. \end{cases} $$
Let $\mathcal{H}_1=\lbrace h1_{(a_1,b_1,a_2,b_2)}: a_1 \le b_1, a_2 \le b_2\rbrace$ and $\mathcal{H}_2=\mathcal{H}_1\cup\lbrace h2_{(a_1,b_1,a_2,b_2)}: a_1 \le b_1, a_2 \le b_2\rbrace$. From the constructions of $\mathcal{H}_1$ and $\mathcal{H}_2$, we can see that $A_{\mathcal{H}_1}(S)=A_{\mathcal{H}_2}(S), \forall S\sim\mathcal{D}^m$ and so $\epsilon_{est_1}=\epsilon_{est_2}$. It's easy to accommodate finiteness by restricting problem to points in $\mathcal{D}$ having integer coordinates and maximum $x$ and $y$ coordinates. And it's contradicting with the statement.
So my question is what is/are the missing condition(s) for the quoted statement to be true.
I asked a similar question here, but the answer is not very satisfactory to me, and since I've found some counter examples for the statement in the book I decided to ask a different question here.
