Probabilistic Variational Bounds for Graphical Models
Variational algorithms such as tree-reweighted belief propagation can provide deterministic bounds on the partition function, but are often loose and difficult to use in an "any-time" fashion, expending more computation for tighter bounds. On the other hand, Monte Carlo estimators such as importance sampling have excellent any-time behavior, but depend critically on the proposal distribution. We propose a simple Monte Carlo based inference method that augments convex variational bounds by adding importance sampling (IS). We argue that convex variational methods naturally provide good IS proposals that "cover" the target probability, and reinterpret the variational optimization as designing a proposal to minimize an upper bound on the variance of our IS estimator. This both provides an accurate estimator and enables construction of any-time probabilistic bounds that improve quickly and directly on state-of-the-art variational bounds, and provide certificates of accuracy given enough samples relative to the error in the initial bound.
The authors propose using an importance sampling procedure based on proposal distributions obtained by running TRW/BP to estimate the partition function of graphical models.They demonstrate experimentally that such methods are effective at constructing good estimates of the partition function for easy instances but are also useful for more challenging instances (though at the price of higher sample complexity).The paper is well-written and more or less self-contained.General thoughts:-There isn't much deep in the way of theoretical content here, so it would have been nice to see how IS with a TRW/BP proposal performs versus other common proposals that are used to estimate partition functions (there is quite a bit of work in this area).The authors make a good point in their rebuttal that this approach does provide bounds which is arguably more useful than simple convergence rates.-Having to actually run TRW/BP to convergence to get the proposal seems unfortunate, and in practice, these methods aren't necessarily particularly fast (especially for large models).Once you do this, you need a large number of additional samples (if the model is hard) to get tight bounds.So, I'm not sure how practical this approach really is.-Z_TRW can be an exponentially bad bound (especially for very frustrated models).This means that \Delta could be quite large.Do you have some sense as to how the number of samples scales with the number of nodes and interaction strength on a single highly frustrated cycle?-On page 7, you mention that LBP is a lower bound on these models and cite [26].Sudderth et al. [26] showed only part of the claimed result under certain conditions on LBP fixed points.The result you are claiming was actually proved later on in:  N. Ruozzi.The Bethe partition function of log-supermodular graphical models.Advances in Neural Information Processing Systems (NIPS), December 2012.Typos:-pg. 1, "optimization and Monte Carlo" -> "optimization and Monte Carlo". -pg. 1, "mean field type" -> "mean-field type". -pg. 2, "important advantages:" -> "important advantages". -pg. 3,It is helpful for readers when expectations use a subscript to denote the distribution with which the expectation is being taken. -pg. 8, "state-of-the-art variational bounds," -> "state-of-the-art variational bounds"