On Learning Monotone DNF under Product Distributions.
R. Servedio.
Information and Computation 193, 2004, pp. 57-74.
Preliminary version in Fourteenth Annual Conference on Computational Learning Theory (COLT), 2001, pp. 558-573.


We show that the class of monotone $2^{O(\sqrt{\log n})}$-term DNF formulae can be PAC learned in polynomial time under the uniform distribution from random examples only. This is an exponential improvement over the best previous polynomial-time algorithms in this model, which could learn monotone $o(\log^2 n)$-term DNF. We also show that various classes of small constant-depth circuits which compute monotone functions are PAC learnable in polynomial time under the uniform distribution. All of our results extend to learning under any constant-bounded product distribution.

pdf of conference version

Postscript or pdf of journal version

Back to main papers page