Approximate maximum entropy principles via Goemans-Williamson with applications to provable variational methods
The well known maximum-entropy principle due to Jaynes, which states that given mean parameters, the maximum entropy distribution matching them is in an exponential family has been very popular in machine learning due to its "Occam's razor" interpretation. Unfortunately, calculating the potentials in the maximumentropy distribution is intractable [BGS14]. We provide computationally efficient versions of this principle when the mean parameters are pairwise moments: we design distributions that approximately match given pairwise moments, while having entropy which is comparable to the maximum entropy distribution matching those moments. We additionally provide surprising applications of the approximate maximum entropy principle to designing provable variational methods for partition function calculations for Ising models without any assumptions on the potentials of the model. More precisely, we show that we can get approximation guarantees for the log-partition function comparable to those in the low-temperature limit, which is the setting of optimization of quadratic forms over the hypercube. ([AN06])
Considering Ising models (with no local fields), a very interesting twist on the standard variational inference approach is developed to show a convex relaxation and rounding that yields a multiplicative factor approximation to log Z. The factor is O(log chi(G)) where chi(G) is the chromatic number of the model graph. For fully attractive (ferromagnetic) models, this improves to a constant factor of 50.
The paper is clear and well written with helpful background and remarks [I have not checked the proofs in detail but the ideas are presented clearly and I trust that the details are correct]. The methods used and results obtained are very interesting. To my knowledge they are novel and may prove useful in other work. Note that a multiplicative bound on Z (hence an additive bound on log Z) would be much stronger and more useful, but as noted in the paper, this is likely impossible. It is not clear how useful these results will be in the near term in practice, but still they are theoretically important and provide good leads for future work.   The authors focus on `symmetric' Ising models with no local fields/singleton potentials, i.e. x_i \in {-1,+1} and E(x_i)=0 for all i. It is worth noting that if an Ising model does have local fields, it can always be transformed into a larger model without any local fields by adding one extra variable and encoding the original singleton potentials as edge potentials to the added variable. The larger model has exactly twice the partition function of the original model, e.g. see Weller ICML 2016, Uprooting and Rerooting Graphical Models.  Further observations on the following would be welcome: A longer comment on the differences between the analysis here and in Ris16 (so expand on lines 84-88 and 105-108). Are there any results/conjectures on what might be the best possible approximation bounds for these problems, so we can see how close these results are?  Minor points:  Section 2 is very helpful as a clear statement of the main results and prior related work. It would be good to tie it to the later text more neatly:  Definition 3.1 of the constant G should come before it is first used in Theorem 2.1. Clarify where exactly Theorems 2.1-2.4 are proved.  line 32: a -> an 33: from from -> than 35-38: very interesting, in 37: delete one 'there' 41: The -> A (there are other important reasons to compute Z) 45-46: Perhaps mention that we know that the Bethe partition function estimate lower bounds the true value (i.e. Z_B \leq Z) for ferromagnetic models, see Ruozzi NIPS 2012, The Bethe partition function of log-supermodular graphical models, and Weller and Jebara NIPS 2014, Clamping variables and approximate inference. 50: If the configuration with max score is not unique, then log Z -> the max * the multiplicity of the max 57: Perhaps mention that better results can be obtained for various restrictions such as bounded treewidth (Wainwright and Jordan 2004,  Treewidth-based conditions for exactness of the Sherali-Adams and Lasserre relaxations) or if certain minors are not present (Weller UAI 2016, Characterizing Tightness of LP Relaxations by Forbidding Signed Minors). 104: Perhaps move the footnote 3 to the end of 103 to save space. 118: theoretically much more poorly studied - not sure if that's true 121: delete 'what' 238: add space between bound) and of. Delete Same. 253: Insert 'a' before rounding 254, 256, 258 should the 2 be (2) as in \eqref References In several places, caps should be fixed, e.g. Grothendieck -> {G}rothendieck. I believe [BB] should be [BB08] from NIPS 2008.