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?


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


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.