Computer Science/Discrete Mathematics Seminar II

We introduce and study a new type of learning problem for probability distributions over the Boolean hypercube \(\{-1,1\}^n\). As in the standard PAC learning model, a learning problem in our framework is defined by a class \(C\) of Boolean functions over \(\{-1,1\}^n\), but unlike the standard PAC model, in our model the learning algorithm is given uniform random satisfying assignments of an unknown \(f \in C\) and its goal is to output a high-accuracy approximation of the uniform distribution over \(f^{-1}(1)\). This distribution learning problem may be viewed as a demanding variant of standard Boolean function learning, where the learning algorithm only receives positive examples and --- more importantly --- must output a hypothesis function which has small *multiplicative* error (i.e. small error relative to the size of \(f^{-1}(1)\)). As our main results, we show that the two most widely studied classes of Boolean functions in computational learning theory ---linear threshold functions and DNF formulas---have efficient distribution learning algorithms in our model. Our algorithm for linear threshold functions runs in time poly\((n,1/\mathrm{eps})\) and our algorithm for polynomial-size DNF runs in time quasipoly\((n,1/\mathrm{eps})\). On the other hand, we prove complementary hardness results which shows that under cryptographic assumptions, learning monotone 2-CNFs, intersections of 2 halfspaces and degree-2 PTFs. This shows that our algorithms are close to what is efficiently learnable in this model. Joint work with Ilias Diakonikolas and Rocco Servedio.