DNF Learning via Locally Mixing Random Walks

We give two results on PAC learning DNF formulas using membership queries in the challenging "distribution-free" learning framework, where learning algorithms must succeed for an arbitrary and unknown distribution over 0, 1 n .

(1) We first give a quasi-polynomial time "list-decoding" algorithm for learning a single term of an unknown DNF formula. More precisely, for any target s-term DNF formula f = T 1 ∨ • • • ∨ T s over 0, 1 n and any unknown distribution D over 0, 1 n , our algorithm, which uses membership queries and random examples from D, runs in quasipoly(n, s) time and outputs a list L of candidate terms such that with high probability some term T i of f belongs to L.

(2) We then use result (1) to give a quasipoly(n, s)-time algorithm, in the distribution-free PAC learning model with membership queries, for learning the class of size-s DNFs in which all terms have the same size. Our algorithm learns using a DNF hypothesis.