2025/05/24 by Alman, Josh, Nadimpalli, Shivam, Patel, Shyamal +1 · 3 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2505.18839
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 = T1 \vee ⋯ \vee Ts 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 \textsfquasipoly(n,s) time and outputs a list L of candidate terms such that with high probability some term Ti of f belongs to L. (2) We then use result (1) to give a \textsfquasipoly(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. The key tool used to establish result (1) is a new result on "locally mixing random walks," which, roughly speaking, shows that a random walk on a graph that is covered by a small number of expanders has a non-negligible probability of mixing quickly in a subset of these expanders.