Marginals-to-Models Reducibility
We consider a number of classical and new computational problems regarding marginal distributions, and inference in models specifying a full joint distribution. We prove general and efficient reductions between a number of these problems, which demonstrate that algorithmic progress in inference automatically yields progress for "pure data" problems. Our main technique involves formulating the problems as linear programs, and proving that the dual separation oracle required by the ellipsoid method is provided by the target problem. This technique may be of independent interest in probabilistic inference.
*** UPDATE following author response *** The 
      reviewers feel the paper would be significantly strengthened by augmenting 
      the paper with some of the additional motivation given in the author 
      response. The particular point that seems most promising to me is: 
      3. Our ellipsoid-based approach is novel and, we hope, will find 
      further applications in the field. Previous polynomial-time solutions to 
      CONSISTENCY generally give a compact (polynomial-size) description of the 
      marginal polytope. Our approach dodges this ambitious requirement, in that 
      it only needs a polynomial-time separation oracle (which, for this 
      problem, turns out to be MAP inference). There are many combinatorial 
      optimization problems with no compact LP formulation that admit 
      polynomial-time ellipsoid-based algorithms (like nonbipartite matching, 
      with its exponentially many odd cycle inequalities). This makes it 
      sound like there is a chance of finding new polynomial-time CONSISTENCY 
      algorithms for a set of models where MAP is tractable but the marginal 
      polytope does not have a compact representation. It would be great if the 
      authors could spell this out. --------------- The authors 
      demonstrate polynomial-time reducibility from several problems 
      relating to consistency of pseudomarginals of a graphical model to the 
      problems of inference in the same graphical model. Specifically, their 
      main result is to show that testing whether a given vector belongs to 
      the marginal polytope of G is polynomial-time reducible to the problem 
      of MAP inference in a graphical model over G. The reduction works by 
      expressing the consistency problem as an LP with exponentially many 
      variables. The dual LP, which has an exponential number of 
      constraints, can be solved in polynomial time by the ellipsoid method 
      if the separation problem can be solved in polynomial time. The 
      required separation oracle is a MAP inference problem over G, which 
      shows the desired reduction. They present related results that follow 
      similar reasoning, e.g., for the problem of finding the closest point 
      in the marginal polytope to a provided vector of pseudomarginals. 
      The paper is technically sound, but it seems incomplete---it ends 
      abruptly without actually presenting several of the results claimed in 
      the introduction. I get the sense the authors ran out of space, time, 
      or both. I took a look at the result in the appendix about MAX-ENTROPY 
      reducing to GENERALIZED-PARTITION. This looks completely standard to 
      me: (1) the dual of the maximum entropy problem (problem D-ME in the 
      paper) is that of maximizing likelihood in an exponential family, (2) 
      this is a convex problem, (3) it can be solved in polynomial time by 
      the ellipsoid algorithm if the log-likelihood function and its 
      gradient can be computed in polynomial time, (4) the log-likelihood 
      function is a linear function minus the log-partition function, so 
      computing it efficiently amounts to computing the log-partition 
      function efficiently. I don't see what the new contribution is. 
      Overall, the authors could do a much better job situating their 
      work in relation to previous work. My initial reaction was to guess 
      that these results would follow from existing results about the theory 
      of exponential family models (cf. Wainwright and Jordan [2]), which 
      already describes very strong connections between marginals and 
      models (e.g., a bijection between marginals and models in a minimal 
      exponential family). I no longer think the main result (Theorem 3.1) 
      follows from that literature, but it would help this paper 
      considerably if the authors could point out the connections and 
      differences. The related work does a very poor job of this 
      currently---it simply points to three standard books/monographs about 
      graphical models. There are some specific connections to prior 
      work that should be mentioned. In particular, the CONSISTENCY problem 
      is exactly that of testing membership in the marginal polytope of G. 
      The authors should mention this explicitly, as much is known about the 
      marginal polytope, and the membership problem which they study has 
      appeared before, and is known to be NP-complete: David Sontag 
      and Tommi Jaakkola, On Iteratively Constraining the Marginal Polytope 
      for Approximate Inference and MAP, Tech. report, 2007 The 
      paper is reasonably clear, but imprecise in a few places, especially 
      surrounding the problem definitions. In particular, the definition of 
      SMALL-SUPPORT is very informal and probably not correct as stated. 
      "Polynomial-size" can only be judged asymptotically; for this case 
      when you have a specific input instance in hand, you probably need to 
      require that the support size is bounded by a specific function of the 
      input size. Also, the MAX-ENTROPY problem as stated seems to want to 
      simulteneuously maximize entropy and minimize the L1 distance from \mu 
      to the marginal polytope. I doubt this is possible. Perhaps you mean 
      to maximize entropy subject to the constraint of \nu being a minimizer 
      of the L1 distance? Regarding novelty and significance, there is 
      really one primary observation in this paper: that MAP inference is 
      the dual separation oracle for the LP formulation of the CONSISTENCY 
      problem (Theorem 3.1). As far as I know, this is new. Several other 
      results (CLOSEST-CONSISTENCY and SMALL-SUPPORT) are slight variants 
      that follow from standard LP tricks. The main result is intriguing, 
      but it is hard to see its significance. The reductions don't point to 
      new algorithms or complexity results for problems that people care 
      about (i.e., CONSISTENCY does not arise in practice, and it does not 
      imply new hardness results for MAP inference). The paper would be 
      strengthened considerably if the authors could point to some 
      application of the results. Minor comments * The 
      characterization of Markov networks and Bayesian networks on line 31 
      seems like it is equating potentials and CPTs with "local marginals". 
      I don't agree with this characterization---potentials are not 
      marginals. The marginal inference problem is all about converting from 
      the potentials to marginals (e.g. [3]). I suggest clarifying the 
      wording here. * Figure 1: the text is very hard to read. * Line 
      121: the number of LP variables is *equal* to the number of joint 
      settings (which is exponential in the number of random variables) 
      * Line 162: This wording/notation suggests that the marginal is the 
      scalar \mu_{is}. I suggest refining the notation (e.g. (\mu_{is}){s 
      \in [k]}) to be more precise, which will clarify that the marginal is 
      a vector. The same comment applies to \mu_{ijst}. * Line 167: "Let 
      M_1 and M_2 denote the indices (i,s) and (i,j,s,t)". This is a bit 
      vague. Can you clarify that M_1 and M_2 are *sets* of indices. * 
      Line 394: Do you mean CLOSEST-CONSISTENCY instead of CONSISTENCY here? 
      * Line 401: mathematical programming --> mathematical program