Learning from positive examples

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∈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/eps) and our algorithm for polynomial-size DNF runs in time quasipoly(n,1/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.