Dynamic Importance Sampling for Anytime Bounds of the Partition Function
Computing the partition function is a key inference task in many graphical models. In this paper, we propose a dynamic importance sampling scheme that provides anytime finite-sample bounds for the partition function. Our algorithm balances the advantages of the three major inference strategies, heuristic search, variational bounds, and Monte Carlo methods, blending sampling with search to refine a variationally defined proposal. Our algorithm combines and generalizes recent work on anytime search [16] and probabilistic bounds [15] of the partition function. By using an intelligently chosen weighted average over the samples, we construct an unbiased estimator of the partition function with strong finite-sample confidence intervals that inherit both the rapid early improvement rate of sampling and the long-term benefits of an improved proposal from search. This gives significantly improved anytime behavior, and more flexible trade-offs between memory, time, and solution quality. We demonstrate the effectiveness of our approach empirically on real-world problem instances taken from recent UAI competitions.
The authors present a method for estimating the partition function that alternates between performing heuristic search and importance sampling.  The estimated value of the partition function is confidence bounded and improves with additional computation time.  Experimental evaluation is performed on problems from 2006 and 2008 UAI competitions by comparing confidence bounds of the proposed method against previous work that uses only sampling [15] or search [16].  The proposed method significantly outperforms sampling on certain problems and search on others, while maintaining performance roughly comparable to or better than either sampling or search across all problems.
The originality of the work is a bit limited, as it is a fairly straightforward (but novel as far as I know) combination of two recent papers, references [15] and [16].
To review past work, [15] proposes a method that combines importance sampling with variational optimization.  The authors chose a proposal distribution that is the solution to a variational optimization problem and show this choice can be interpreted as picking the proposal distribution that minimizes an upper bound on the value of importance weights.  The importance weight bound is then used to construct a (probabilistic, but with confidence intervals) bound on the estimate of the partition function.
[16] describes a search algorithm for computing deterministic bounds on the partition function.  Unlike deterministic bounds given by variational methods, the search algorithm proposed in [16] can continue to improve its estimate in an anytime manner, even when given limited memory resources.  
This paper combines the methods of approaches of [15] and [16] by alternating between importance sampling and search.  Search is performed using a weighted mini-bucket variational heuristic.  The same mini-buckets are used to improve the proposal distribution over time, generating better samples.  The authors provide a method for weighting later samples more heavily as the proposal distribution improves.  
The authors demonstrate that the proposed method improves estimation of the partition function over state of the art sampling and search based methods ([15] and [16]).  There is room for researchers to build on this paper in the future, particularly in the areas of weighting samples generated by a set of proposal distributions that improve with time and exploring when computation should be focused more on sampling or search.
The paper is clear and well organized.  Previous work the paper builds on is well cited.  
Minor:
- Line 243 states that DIS remains nearly as fast as AOBFS in figures 3(d) and (f), but it appears that the lower bound of DIS converges roughly half an order of magnitude slower.  Line 233 states, "we let AOBFS access a lower bound heuristic for no cost."  Does the lower bound converge more slowly for DIS than AOBFS in these instances or is the lower bound shown for AOBFS unfair?
- Line 190, properites is a typo.
- Line 146 states that, "In [15], this property was used to give finite-sample bounds on Z which depended on the WMB bound, h_{\emptyset}^{+}."  It appears that in [15] the bound was only explicitly written in terms of Z_{trw}.  Mentioning Z_{trw} may make it slightly easier to follow the derivation from [15].