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?


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

  • $\begingroup$ That is a remarkable lemma. By definition if $H$ is not PAC learnable, there must be some degree of reliability $(\epsilon, \delta)$ small enough that for any $n$, the algorithm fails to be that reliable on samples of size $n$. Your version of the NFL theorem implies that $(\epsilon, \delta)$, if it exists, can always be chosen to be $(1/8, 1/7)$. That's as if there were some "magic number" like $1/8$ such that any sequence which isn't eventually within $1/8$ of a number $L$ does not converge to $L$, or equivalently, any sequence which is eventually within $1/8$ of $L$ does converge to $L$. $\endgroup$
    – Jack M
    Commented Oct 11, 2020 at 17:33

Your Answer

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

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