Are PAC learnability and the No Free Lunch theorem contradictory?

Question

I am reading the Understanding Machine Learning book by Shalev-Shwartz and Ben-David and based on the definitions of PAC learnability and No Free Lunch Theorem, and my understanding of them it seems like they contradict themselves. I know this is not the case and I am wrong, but I just don't know what I am missing here.

So, a hypothesis class is (agnostic) PAC learnable if there exists a learner A and a function $m_{H}$ s.t. for every $\epsilon,\delta \in (0,1)$ and for every distribution $D$ over $X \times Y$, if $m \geq m_{H}$ the learner can return a hypothesis $h$, with a probability of at least $1 - \delta$ $$ L_{D}(h) \leq min_{h'\in H} L_{D}(h') + \epsilon $$

But, in layman's terms, the NFL theorem states that for prediction tasks, for every learner there exists a distribution on which the learner fails.

There needs to exists a learner that is successful (defined above) for every distribution $D$ over $X \times Y$ for a hypothesis to be PAC learnable, but according to NFL there exists a distribution for which the learner will fail, aren't these theorems contradicting themselves?

What am I missing or misinterpreting here?

Answer 1

There is no contradiction. First, agnostic PAC learnable doesn't mean that the there is a good hypothesis in the hypothesis class; it just means that there is an algorithm that can probably approximately do as well as the best hypothesis in the hypothesis class.

Also, these NFL theorems have specific mathematical statements, and hypothesis classes for which they apply are often not the same as the hypothesis class for which PAC-learnability holds. For example, in Understanding Machine Learning by Shalev-Shwartz and Ben-David, a hypothesis class is agnostic PAC learnable if and only if has finite VC dimension (Theorem 6.7). Here, the algorithm is ERM. On the other hand, the application of the specific version of NFL that this book uses has Corollary 5.2, that the hypothesis class of all classifiers is not PAC learnable, and note that this hypothesis class has infinite VC dimension, so the Fundamental Theorem of PAC learning does not apply.

The main takeaway is that in order to learn, we need some sort of inductive bias (prior information). This can be seen in the form of measuring the complexity of the hypothesis class or using other tools in learning theory.

Answer 2

(All notations based on Understanding ML: From Theory to Algorithms) The layman's term for NFL is super misleading. The comparison between PAC learnability and NFL is kind of baseless since both proof's are built on a different set of assumptions.

Let's review the definition of PAC learnability:

A hypothesis class $H$ is PAC learnable if there exist a function $m_H : (0, 1)^ 2 → N$ and a learning algorithm with the following property: For every $\epsilon, \delta \in (0, 1)$, for every distribution $D$ over $X$ , and for every labelling function $f : X → {0, 1}$, if the realizable assumption holds with respect to $H, D, f$ , then when running the learning algorithm on $m ≥ m_H (\epsilon, \delta)$ i.i.d. examples generated by $D$ and labeled by $f$ , the algorithm returns a hypothesis $h$ such that, with probability of at least $1 − δ$ (over the choice of the examples), $L_{(D,f )} (h) ≤ \epsilon$.

An important point in this definition is that the complexity bounds (i.e value of $m$) holds irrespective of distribution $D$ (this is known as distribution free). Since, in the proofs we assume error to be $1$ i.e if $f(x) \neq h(x)$ then we assign error $=1$ so $L_D(A(S))$ which is defined as the true probability of error by the classifier ($A(S) = h_S$) will be the same as $\Bbb E_{S \sim D^{m}}(h_S)$. Also, the realizable assumption is not very important here.

Now let's review the definition of NFL:

Let $A$ be any learning algorithm for the task of binary classification with respect to the $0 − 1$ loss over a domain $X$ . Let $m$ be any number smaller than $|X |/2$, representing a training set size. Then, there exists a distribution $D$ over $X × \{0, 1\}$ such that:

1. There exists a function $f : X → \{0, 1\}$ with $L_{D} (f ) = 0$ (i.e.Realizable).
2. With probability of at least $1/7$ over the choice of $S \sim D^m$ we have that $L_D (A(S)) ≥ 1/8$.

NOTE: For second statement it suffices to show that $\Bbb E_{S \sim D^{m}}L_D(A'(S)) \geq 1/4$, which can be shown using Markov's Inequality. Also, the definition is implying we consider all functions possible from $X × \{0, 1\}$ and our learning algorithm can pick any function $f$ out of this, which somewhat implies that the set $X$ has been shattered.

If you read the definition it clearly states there exists a $D$, which is clearly different from distribution free assumption of PAC learnability. Also to note that we are restricting sample size $m$ to $|X |/2$. You will be able to falsify the second statement by simply picking bigger $m$ and thus your class is suddenly PAC learnable. Thus the point NFL is trying to make is that:

Without an inductive bias i.e if you pick all possible functions from $f : X → {0, 1}$ as your hypothesis class you would not be able to achieve for all $D$ an accuracy less than $1/8$ with probability greater than $6/7$ given your sample size is at most $|X|/2$.

To prove this, you only have to pick a distribution for which this holds. In the proof of the book they have used the uniform distribution which is the margin between 2 types of distribution. So the idea is lets say you have sampled $m = \frac{|X|}{2}$ points, your learning algorithm returns a hypothesis as per ERM rule (doesn't really matter) on the sampled points. Now you want to comment on the error over $2m$ points and true distribution (uniform distribution in this case). So clearly, the probability of picking a point outside your sampled points (unseen points) is $0.5$. Also, the $A(S) = h_S$ will have a $0.5$ probability of agreeing with the actual label of an unseen point (among all $h$ which agree with the sampled points, half will assign $1$ to an unseen point while other half will assign $0$), which makes the total probability of making an error$=0.25$ over the true distribution or $\Bbb E_{S \sim D^{m}}L_D(A(S)) = 1/4$

Note, that we have picked up uniform distribution but this will also hold for distributions which assigns probability $p \leq 0.5$ on the sampled points, then the probability of picking a point outside your sampled points (unseen points) is $\geq 0.5$ and thus error is $\geq 0.5$, and thus uniform distribution is the mid point. ANother important point to note is that if we pick $m+1$ points we will definitely do better, but then its kind of overfitiing.

This basically translates to why infinite VC dimension hypothesis class is not PAC learnable, because it shatters every set of size $|X|$ and we have already seen the implications of picking a hypothesis class which shatters a set of size $|X|$ in NFL.

This is the informal description of how the NFL theorem was arrived at. You can find the entire explanation in this lecture after which the proof in the book will start to make much more sense.

Thus, inductive bias (restricting hypothesis class to some possible good candidates of $h$) is quite important as can be seen, the effects without any inductive bias.

Answer 3

There is no contradiction between PAC learning and the no-free-lunch theorem as commented in other answers.

But there is indeed a contradiction between the no-free-lunch theorem and its layman's explanation:

• for infinite $\mathcal{X}$, whenever $\mathcal A$ is fixed, there is a distribution on which it fails to learn.

This is not true!

Indeed, if $\mathcal X$ is countable and $\mathcal A$ is an algorithm that simply memorizes what it has seen and answers $0$ for unseen samples, then it can be shown that the true error of $\mathcal A$ converges to $0$, so $\mathcal A$ effectively learns. (See page 95)

For uncountable $\mathcal X$, the layman's explanation is correct. In that case, the theorem looks rather obvious, because finite samples provide no information about the behavior of the true mapping $f$, except at a null set.

I personally dislike that part of the book (page 61), because immediately before the no-free-lunch theorem, they say literally "no learner can succeed on all learning task, as formalized in the following theorem:", but they leave the distribution $\mathcal D$ as dependent on $m$ in the theorem statement, which disrupts all the previous definitions of learnability and makes the introductory phrase (the layman's terms) misleading.

Answer 4

PAC-learning is a definition and imposes a condition ("if, for all distribution, and other conditions are met then...") that, if met, then the class is PAC-learnable.

NFL Theorem is a result: There is always a distribution that makes the learner not learn.

The main observation: the statement of the NFL Theorem does not specify which class $\mathcal{H}$ the learner is using, so it manages to prove that the learner fail miserably.

Conclusion: if $\mathcal{H}$ is not restricted in some way, then the NFL theorem is valid. However, if we restrict $\mathcal{H}$, then - maybe - the conditions of the PAC-learning definition will be met.

For example, some successful learners (as presented in the "Understanding Machine Learning" book, right after the NFL statement):

• ERM with $\mathcal{H} = \{f\}$
• ERM with $\mathcal{H}$ finite that contains $f$ and whose size satisfies $m \ge 8 \log(7|\mathcal{H}|/6)$ (Corollary 2.3)

These learners respect item (1) of the NFL theorem statement ("exists $f: \mathcal{X} \rightarrow \{0,1\}$ with $L_{\mathcal{D}}(f)=0$") because they restrict $\mathcal{H}$.