Title: Learning from Satisfying Assignments
Speaker: Rocco Servedio, Columbia University
Date: Wednesday, November 13, 2013 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We introduce and study a new type of learning problem for probability distributions over the Boolean hypercube. As in the standard PAC learning model, a learning problem in our framework is defined by a class C of Boolean functions over the hypercube, but unlike the standard PAC model, in our model the learning algorithm is given uniform random satisfying assignments of an unknown function in C and its goal is to output a high-accuracy approximation of the uniform distribution over the space of satisfying assignments for f. 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/epsilon) and our algorithm for polynomial-size DNF runs in quasipolynomial time. On the other hand, we also prove complementary hardness results which show that under cryptographic assumptions, learning monotone 2-CNFs, intersections of 2 halfspaces, and degree-2 PTFs are all hard. This shows that our algorithms are close to the limits of what is efficiently learnable in this model.
Joint work with Anindya De and Ilias Diakonikolas.
See: http://www.math.rutgers.edu/~sk1233/theory-seminar/F13/