$L_\mathcal{D}(A(S)) \le 0.1$ with prob at least $0.9$ implies PAC learnability

Question

Suppose we have a hypothesis class $\mathcal{H}$ that is non-uniform learnable via sample compelxity function $m_{\text{NUL}}:[0,1]^2 \times \mathcal{H} \rightarrow \mathbb{N}$. If we define $\mathcal{H}_n=\{h \in \mathcal{H}: m_{\text{NUL}}(0.1,0.1,h) \le n\}$, why is $\mathcal{H}_n$ PAC-learnable?

This argument is used in proof of theorem 7.2 in this book http://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf

It is stated that, by assuming realizability, using the same learning algorithm $A$, with probability at least $0.9$ over sample $S \sim \mathcal{D}^n$, we have $L_{\mathcal{D}}(A(S)) \le 0.1$. But I don't see immediately why this is PAC-learnable because we should be able to compress the error below any $\epsilon$ with arbitrarily high probability $1-\delta$. What is the trick?

Answer 1

The end of the proof of Theorem 7.2 explicitly states "Using the fundamental theorem of statistical learning, this implies that the VC dimension of $\mathcal{H}_n$ must be finite, and therefore $\mathcal{H}_n$ is agnostic PAC learnable."

Now, this is confusing, since looking at this "fundamental theorem of statistical learning" (Theorem 6.7 in this book), it looks like we want to use the implication $(4) \Rightarrow (6)$, namely PAC learnability implies finite VC dimension. But, as you point out, instead of PAC learnability we only have the seemingly weaker guarantee you wrote:

With probability at least $6/7$ over $S\sim \mathcal{D}^m$ we have $L_{\mathcal{D}}(A(S))\leq 1/8$

using the notation of the book. However, if you look at the proof of Theorem 6.7, $(4) \Rightarrow (6)$ follows from the No-Free-Lunch theorem (Theorem 5.1), or rather its implication in terms of VC dimension (Corollary 6.4, and then Theorem 6.6). I'll let you check the details, but essentially it proves the stronger-looking statement you need:

Let $\mathcal{H}$ be a class of infinite VC dimension. Then, for every $m$, and every learning algorithm $A$, there exists a distribution $\mathcal{D}$ and a predictor $h\in\mathcal{H}$ such that (i) $L_{\mathcal{D}}(h) = 0$; but (ii) with probability at least $1/7$ over $S\sim \mathcal{D}^m$ we have $L_{\mathcal{D}}(A(S)) > 1/8$.