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?

  • 1
    $\begingroup$ PAC learnability is about learning approximately and probably. In fact, PAC stands for probably approximately correct. It doesn't (necessarily) guarantee that you will learn the correct hypothesis with probability 1. I am not familiar with the details of the NFL theorem(s), so I cannot say more now, but a proper answer to your question probably includes this information I've just mentioned. $\endgroup$
    – nbro
    Feb 2 '20 at 20:20
  • $\begingroup$ I do take that into consideration. The NFL theorem also defines the failure of a learner in terms of a probability $(1- \delta)$ and an error threshold $\epsilon$ $\endgroup$ Feb 2 '20 at 20:34

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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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