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} $$


$$ 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.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.