Valiant's theory of PAC learning looks at the tradeoff between expected error and algorithm runtime in different classes of learning problems. In particular, a lot of his analysis focuses on which classes of disjunctive normal form (DNF) formulae are learnable in polynomial time while minimizing expected error (PAC learnable).

However, many classes of DNF formulae are not PAC learnable. This means that learning takes an exponential amount of time based on the number of variables $N$ in the formula, i.e. the algorithm runtime is $O(2^N)$.

I assume that the DNF formula that is learned in this case is not the minimal DNF formula, since it is NP-Hard to do so, meaning the complexity is $O(2^{2^N})$.

If so, then this is confusing to me.

Say there are $2^{10}-5$ samples from $f$, and the algorithm has to predict the remaining 5 bits. If my understanding of PAC learning is correct, there is an algorithm that should be able to accurately predict the 5 bits in $O(2^N)$ time.

However, it also seems to me that to accurately predict the 5 bits the algorithm has to figure out which of the $2^{5}$ different ways of filling in the bits has the shortest DNF formula, due to Occam's razor. But, if the algorithm has to figure out the shortest DNF formula in each of the $2^5$ permutations, then it has to perform logic minimization, which has a runtime of $O(2^{2^N})$. Then, that means that if a DNF formula is not PAC learnable, its runtime is super-exponential, not exponential.

So, which is it? Does a DNF being not PAC learnable mean the algorithm's runtime is $O(2^N)$ or $O(2^{2^N})$?


1 Answer 1


There's a misconception here. PAC learning doesn't require the learning to find the shortest formula. It merely requires the learner to find any formula that has sufficiently low generalization error. If there are multiple formulas that meet that criteria, the learner is allowed to output any of them -- not necessarily the shortest.

Take a closer look at the formal definition, and hopefully you'll see how that follows from the definition.


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.