Hardness of parameter estimation in graphical models
We consider the problem of learning the canonical parameters specifying an undirected graphical model (Markov random field) from the mean parameters. For graphical models representing a minimal exponential family, the canonical parameters are uniquely determined by the mean parameters, so the problem is feasible in principle. The goal of this paper is to investigate the computational feasibility of this statistical task. Our main result shows that parameter estimation is in general intractable: no algorithm can learn the canonical parameters of a generic pair-wise binary graphical model from the mean parameters in time bounded by a polynomial in the number of variables (unless RP = NP). Indeed, such a result has been believed to be true (see [1]) but no proof was known. Our proof gives a polynomial time reduction from approximating the partition function of the hard-core model, known to be hard, to learning approximate parameters. Our reduction entails showing that the marginal polytope boundary has an inherent repulsive property, which validates an optimization procedure over the polytope that does not use any knowledge of its structure (as required by the ellipsoid method and others).
This paper studies the worst case hardness of estimating the parameters of abinary pairwise undirected graphical model. By considering the specific case ofthe hard-core / independent set model and relying on the known result thatapproximating the partition function for this problem given the parameters (evenfor the "unweighted" case of all theta_i being 0) is hard, the authors show thatthe other direction -- namely, approximating the parameters given the nodemarginals -- is hard, in the sense that it does not admit an FPRAS.This is a strong theoretical paper, addressing a computational complexityproblem that occurs very often in theory and practice, has been conjectured tobe hard, but hadn't yet been shown formally to be hard (to the best of my andthe authors' knowledge). The work is unlikely to have much impact in practice.Nonetheless, it provides new insights into the parameter estimation problemthrough the structure of their reduction, which essentially says that if onecould efficiently approximate the parameters given the marginals, then one coulduse the projected gradient method to efficiently estimate the marginals giventhe parameters (in particular, when theta_i = 0), which in turn is known to behard.The technique used in the proof, specifically that it suffices to activelyproject on to a quadrant and yet indirectly achieve projection onto the shrunkenpolytope M_1, is the main novelty. The overall reasoning seems correct: I couldnot identify any significant flaws, however I have not verified the details ofall proofs, especially those in the supplementary material.The paper is written well and often provides abstract summaries of the technicalstatements/claims to follow. One aspect that could improve the paper (or perhapsis already there but I missed) is a clear intuitive description of thereduction, along the lines that one can efficiently approximate thehard-to-approximate \theta -> \mu problem (specifically for \theta = 0) if onehad an efficient approximation to the \mu -> \theta problem, using anoptimization method that is guaranteed to involve only a polynomial number ofsteps.Minor comments:- Depending on the background of the readers, they may be very familiar with one  of 'hard-code model' and 'independent set' problems, but likely not with both.  Clarifying early on that both are the same (where for the independent set  problem one associates a weight lambda_i with each node, which then induces a  weight on every independent set) would help such readers.- In Theorem 3.1, did you mean to write lambda = 1 and d >= 6 (rather than 5)?  Otherwise it seems that lambda will be less than (d-1)^{d-1} / (d-2)^d.- In several places, inline math expressions of the form abc/def are ambiguous.  I believe in most places you mean abc/(def) rather than (abc/d) * ef. It would  be better to remove than ambiguity.- Page 3, in the top-third: in what sense is the marginal polytop M a polytope  "equal to the convex hull of independent set vectors I(G)"?- Definition 2.1: missing "y" after (1+delta).- Corollary 3.2: "degree most d" -> "degree at most d"