Concavity of reweighted Kikuchi approximation
We analyze a reweighted version of the Kikuchi approximation for estimating the log partition function of a product distribution defined over a region graph. We establish sufficient conditions for the concavity of our reweighted objective function in terms of weight assignments in the Kikuchi expansion, and show that a reweighted version of the sum product algorithm applied to the Kikuchi region graph will produce global optima of the Kikuchi approximation whenever the algorithm converges. When the region graph has two layers, corresponding to a Bethe approximation, we show that our sufficient conditions for concavity are also necessary. Finally, we provide an explicit characterization of the polytope of concavity in terms of the cycle structure of the region graph. We conclude with simulations that demonstrate the advantages of the reweighted Kikuchi approach.
This paper considers the so-called reweighted version of the Kikuchi variational approximation of the partition function, and provides sufficient conditions under which the variational objective is concave and hence can be optimized more effectively. The conditions are shown to be necessary under additional assumptions. Some experimental results on synthetic problems are shown to confirm the theoretical predictions.The paper is interesting and well written. It provides the necessary background and it does a good job explaining the results at an intuitive level and placing them into the context of what was previously known. As far as I know the results are novel, and they are a nice contribution to our understanding of variational approximations to the partition function. The results should be of interest for the sub-community of NIPS working on message passing and variational techniques. It's another step forward towards better understanding these techniques and their empirical success. One limitation is that it's a bit unclear if the work has practical implications. For example, it does not introduce any new algorithmic approach to the problem (in the experimental results section, they use the reweighted sum product algorithm of Wainwright et al). It's great that we get a better understanding and we can guarantee convexity and hence convergence, but does the theory provide any a-priori indication on how to set $rho$ for a practitioner? It seems that in practice rho_cycle and rho_tree are fairly close to each other and the corresponding approximations do not differ much.In the plot in figure 1(d), it seems that the error increases by going from rho_tree to rho_cycle, and it starts underestimating the value of the partition function. Am I reading it correctly? Is that a counterexample that the approximation is not always better and there is no hope it provides an upper bound up to rho_cycle? Minor:Line 126: I am curious why it "is not in general convex". Isn't a convex combination of two realizable marginals (points in Delta_R, say realized by tau_1 and tau_2) realizable by taking a convex combination of tau_1 and tau_2 with the same coefficients?