Why is learning DNF harder than learning CNF?

Question

In the PAC-learning setting, it is easy to learn a CNF formula when we know each clause has at most $c$ variables.

We go through each positive sample, and eliminate every clause that contradicts the sample.

Learning a DNF formula is said to be much harder, but it seems a similar procedure can be used, so it is unclear to me why DNF is more difficult.

Start with all conjuctive clauses that have at most $c$ variables. Go through each negative sample, and eliminate clauses that contradict the sample.

Answer 1

It's important to distinguish between $k$-CNF and CNF. A $k$-CNF formula is a CNF formula where every clauses has at most $k$ literals; a CNF formula has no limit on the number of literals in each clause.

Both $k$-CNF and $k$-DNF are efficiently, properly PAC learnable, when $k$ is constant. In contrast, as far as I am aware, it is not known whether CNF or DNF are efficiently, properly PAC learnable (no PAC-learning procedure is known for either). So there is no asymmetry.

By "efficiently, properly PAC learnable", I mean that there is a polynomial-time algorithm for PAC learning, where the hypothesis space is the same as the concept space (e.g., given labelled instances from a $k$-CNF formula $\phi$, we want to find a $k$-CNF formula $\phi'$ that has low generalization error).

Since you haven't provided any references nor told us where you got the impression that $k$-DNF isn't PAC-learnable, it's hard to know what the exact source of your misconception might be.