Timezone: »

Embed and Project: Discrete Sampling with Universal Hashing
Stefano Ermon · Carla Gomes · Ashish Sabharwal · Bart Selman

Thu Dec 05 07:00 PM -- 11:59 PM (PST) @ Harrah's Special Events Center, 2nd Floor

We consider the problem of sampling from a probability distribution defined over a high-dimensional discrete set, specified for instance by a graphical model. We propose a sampling algorithm, called PAWS, based on embedding the set into a higher-dimensional space which is then randomly projected using universal hash functions to a lower-dimensional subspace and explored using combinatorial search methods. Our scheme can leverage fast combinatorial optimization tools as a blackbox and, unlike MCMC methods, samples produced are guaranteed to be within an (arbitrarily small) constant factor of the true probability distribution. We demonstrate that by using state-of-the-art combinatorial search tools, PAWS can efficiently sample from Ising grids with strong interactions and from software verification instances, while MCMC and variational methods fail in both cases.

Author Information

Stefano Ermon (Stanford)
Carla Gomes (Cornell University)
Ashish Sabharwal (IBM Watson Research Center)
Bart Selman (Cornell University)

More from the Same Authors