Embed and Project: Discrete Sampling with Universal Hashing
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.
The paper presents and evaluates a new method to 
      sample from complex high-dimensional distributions by reducing the problem 
      to a small number of related optimization and enumeration problems. It is 
      shown that with high probability the sampling distribution is within a 
      constant factor from the true distribution. Experimental results 
      demonstrate cases where the proposed method outperforms standard MCMC and 
      variational methods. The work continues on a great series of 
      earlier studies on how sampling and counting problems can be solved by 
      using solvers for SAT and other hard combinatorial problems. The 
      approach is well motivated by the fact that existing solvers tend to be 
      very fast on typical instances encountered in practice, even if the 
      problems are NP-hard and the solvers' worst-case runtime guarantees look 
      rather hopeless. Prior works in this research direction (after the early 
      works of Valiant, Vazirani, and Jerrum) are chiefly by Gomes, Sabharwal, 
      Selman et al.: 1. Carla P. Gomes, Ashish Sabharwal, Bart 
      Selman: Near-Uniform Sampling of Combinatorial Spaces Using XOR 
      Constraints. NIPS 2006: 481-488 2. Carla P. Gomes, Ashish 
      Sabharwal, Bart Selman: Model Counting: A New Strategy for Obtaining 
      Good Bounds. AAAI 2006: 54-61 3. Carla P. Gomes, Jörg Hoffmann, 
      Ashish Sabharwal, Bart Selman: Short XORs for Model Counting: From 
      Theory to Practice. SAT 2007: 100-106 4. Carla P. Gomes, Jörg 
      Hoffmann, Ashish Sabharwal, Bart Selman: From Sampling to Model 
      Counting. IJCAI 2007: 2293-2299 5. Carla P. Gomes, Willem Jan van 
      Hoeve, Ashish Sabharwal, Bart Selman: Counting CSP Solutions Using 
      Generalized XOR Constraints. AAAI 2007: 204-209 6. Stefano Ermon, 
      Carla P. Gomes, Bart Selman: Uniform Solution Sampling Using a 
      Constraint Solver As an Oracle. UAI 2012: 255-264 7. Stefano 
      Ermon, Carla P. Gomes, Ashish Sabharwal, Bart Selman: Taming the Curse 
      of Dimensionality: Discrete Integration by Hashing and Optimization. ICML 
      2013 8. Stefano Ermon, Carla P. Gomes, Ashish Sabharwal, Bart 
      Selman: Optimization With Parity Constraints: From Binary Codes to 
      Discrete Integration. UAI 2013 While the series as a whole 
      constitutes a major innovation in the counting and sampling methodology, 
      the present contribution is rather incremental. The main message of the 
      paper, namely that combinatorial optimization and search tools enable 
      sampling from complex distributions with controllable accuracy guarantees, 
      follows already from the WISH algorithm given in the ICML'13 paper (7), 
      since it is well known (e.g., due to Jerrum, Valiant, Vazirani) that 
      accurate counting enables accurate sampling (supposing the problem is 
      self-reducible in a way they often are). The proposed algorithm, PAWS, 
      however does not implement that reduction: PAWS takes, in a sense, a more 
      direct route to turn optimization and solution enumeration tools into a 
      sampling algorithm. Only a single optimization instance needs to be 
      solved, under the original combinatorial domain, which seems like a 
      significant advantage. The downside is that one has to solve several 
      enumeration instances in a much larger and more complicated domain. Under 
      what conditions is PAWS more efficient than WISH (whether for sampling or 
      integration)? The paper does not give even a preliminary answer to this 
      question. In particular, the experiments reported in Figure 1 concern a 
      variant of WISH that faster but potentially much less accurate than the 
      original WISH. The presentation is mostly excellent. The title and 
      the abstract are particularly well written and informative, close to 
      perfect. In Sections 3.2 and 3.3 there is, however, room for improvement: 
      Def2 is difficult to follow at first glance. The description of the 
      algorithm around Lemmas 3 and 4 gets dense and almost impossible to follow 
      for a reader that is not familiar with the cited works [3,5,6]. While I 
      appreciate the rigorous statements of Lemmas 3 and 4, I'd like to see an 
      expanded description of the key ideas. Why is it so interesting whether 
      the hashed space contains at least P solutions? What is the role of k? To 
      get more space, I'd consider removing Corollary 2 and the Conclusions 
      section. - I'd use a bold font for emphasizing purposes only 
      when defining new concepts. - Just before Def1 I'd avoid 
      "log-likelihood" because of the association to the likelihood function (of 
      model parameters) that assumes some data are around. - Sentences that 
      end with a displayed equation should end with a ".". - In Def2 I'd 
      write write M/r^\ell < w(x) \leq M/r^i . - In Section 3.3 use the 
      reference numbers, e.g. [6], as parenthetical information, removing of 
      which leaves an intelligent sentence. - Consider placing the caption 
      of Figure 2 below the figure.