# What is the condition under which the estimation error increases (logarithmically) with hypothesis class size for a finite hypothesis class

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.