# Learning from positive examples

 Computer Science/Discrete Mathematics Seminar II Topic: Learning from positive examples Speaker: Anindya De Affiliation: Member, School of Mathematics Date: Tuesday, November 5 Time/Room: 10:30am - 12:30pm/West Bldg. Lect. Hall Video Link: https://video.ias.edu/csdm/2013/1105-AnindyaDe

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.