Skip to content Skip to navigation
Seminar
11/13/2013 11:00 am
CoRE 431

Learning from satisfying assignments

Rocco Servedio, Columbia University

Organizer(s): Swastik Kopparty and Shubhangi Saraf

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.