Learning random monotone DNF

摘要

We give an algorithm that with high probability properly learns random monotone DNF with t(n) terms of length ≈logt(n) under the uniform distribution on the Boolean cube {0,1}n. For any function t(n)≤poly(n) the algorithm runs in time poly(n,1/ε) and with high probability outputs an ε-accurate monotone DNF hypothesis. This is the first algorithm that can learn monotone DNF of arbitrary polynomial size in a reasonable average-case model of learning from random examples only. Our approach relies on the discovery and application of new Fourier properties of monotone functions which may be of independent interest.