Gauging Variational Inference
Computing partition function is the most important statistical inference task arising in applications of Graphical Models (GM). Since it is computationally intractable, approximate methods have been used in practice, where mean-field (MF) and belief propagation (BP) are arguably the most popular and successful approaches of a variational type. In this paper, we propose two new variational schemes, coined Gauged-MF (G-MF) and Gauged-BP (G-BP), improving MF and BP, respectively. Both provide lower bounds for the partition function by utilizing the so-called gauge transformation which modifies factors of GM while keeping the partition function invariant. Moreover, we prove that both G-MF and G-BP are exact for GMs with a single loop of a special structure, even though the bare MF and BP perform badly in this case. Our extensive experiments indeed confirm that the proposed algorithms outperform and generalize MF and BP.
The paper presents two new approaches to variational inference for graphical models with binary variables - an important fundamental problem. By adding a search over gauge transformations (which preserve the partition function) to the standard variational search over (pseudo-)marginals, the authors present methods called gauged mean field (G-MF, Alg 1) and gauged belief propagation (G-BP, Alg 2). Very helpfully, both are guaranteed to yield a lower bound on the true partition function - this may be important in practice and enables empirical testing for improved performance even for large, intractable models (since higher lower bounds are better). Initial experiments demonstrate the benefits of the new methods.
The authors demonstrate technical skill and good background knowledge. The new approaches seem powerful and potentially very helpful in practice, and appear very sensible and natural when introduced in Sec 3.1 given the earlier background. The discussion and extensions in Sec 3.2 are interesting. Theorem 1 is a strong theoretical result - does it hold in general for a graph with at most one cycle?
However, I have some important questions/concerns. If these were fixed, then this could be a strong paper:
1. Algorithm details and runtime.
Both algorithms require a sequence of decreasing barrier terms \delta_1 > \delta_2... but I don't see any comments on how these should be set? What should one do in practice and how much impact could this have on runtime and accuracy?
There appear to be no comments at all on runtime. Both algorithms will likely take much longer than the usual time for MF or BP. 
Are we guaranteed an improvement at each iteration? Even if not, because we always have a lower bound, we could use the max so far to yield an improving anytime algorithm.
Without any runtime analysis, the empirical accuracy comparisons are not really meaningful. There are existing methods which will provide improved accuracy for more computation, and comparison would be very helpful (e.g. AIS or clamping approaches such as Weller and Jebara NIPS 2014; or Weller and Domke AISTATS 2016, which shows monotonic improvement for MF and TRW when each additional variable is clamped).
Note that with clamping methods: if a model has at most one cycle, then by clamping any one variable on the cycle and running BP, we obtain the exact solution (compare to Theorem 1).
More generally, if sufficient variables are clamped st the remainder is acyclic then we obtain the exact solution. Of course, for a graph with many cycles this might take a long time - but this shows why considering accuracy vs runtime is important.
What is the quality of the marginals returned by the new approaches? Does a better partition function estimate lead to better marginals?
2. Explanation of the gauge transformation.
Given the importance here of the gauge transformation, which may be unfamiliar to many readers, it would help significantly if the explanation could be expanded and at least one example provided. I recognize that this is challenging given space constraints - even if it were in the Appendix it would be a big help.
l. 177-179 please elaborate on why (8) yields a lower bound on the partition function.
Minor details:
1.238-240 Interesting that G-BP performs similarly to BP for log-supermodular models. Any further comment on this?
If/when runtime is added, we need more details on which method is used for regular BP.
A few typos -
l. 53 alternative -> alternating (as just defined in the previous sentence). I suggest that 'frustrated cycle' may be a better name than 'alternating cycle' since a balanced cycle of even length could have edge signs which alternate.
l. 92 two most -> two of the most
l. 134-5 on the expense of making underlying -> at the expense of making the underlying
In Refs, [11] ising -> Ising; [29] and [30] bethe -> Bethe