(Sep 03 3-5pm) Meeting Summary: Convex Relaxations for MAP Estimation (Kumar, Kolmogorov, Torr)


We discussed the various types of relaxations of the original IP for MAP estimation, where the two non-convex constraints are the integer constraint {1, -1} on the variables, and the constraint that .  In general, it was assumed that the tightest relaxation was the SDP relaxation (though also the most computational demanding), followed by SOCP and QP, with LP being the least tight of the relaxations.

However, this paper showed that, using only certain SOC constraints associated with edges of the MRF, that the SOCP was equivalent to the QP, and both were dominated by the LP.  We discussed the notion of dominance, and why it makes sense that, for the minimization problem, a relaxation dominates a second relaxation if the first has a greater minimum value than the second.  One key to understanding this is to see that every relaxation uses a feasible set that is a super set of the original problem, thus the original problem has a greater minimum value than every relaxation (why?) and hence dominates every relaxation, as would be expected.

It took me a little while to prove the facts stated in the paper regarding , on page 95 below equation (46) and at the beginning of page 96.  The set on page 95 can be proved by considering the different cases of positive and negative , for instance , with .  The first inequality on page 96 is easy to prove (in fact I think it’s an equality).  The second inequality can be proven by using the fact that the geometric average is always less than or equal to the arithmetic average.

The final section of the paper deals with ways of moving forward, given the theoretical results of the paper.  One thing to do is to simply add the linear marginalization constraints to the SOCP, rather than using the SOC constraints on edges.  Cycle inequality SOC constraints can be added to the SOCP (to get SOCP-C), but linear cycle inequalities can also be added to the LP.  The paper ends by giving additional SOC constraints on cliques (SOCP-Q), results in a feasible region that is not a super set of the corresponding LP feasible region.

The takeaway message is that, only using the straightforward SOC constraints on edges is actually dominated by the LP.  In general, SOCP is seen as a balance between LP and SDP, but in order to do better than LP, additional SOC constraints must be used.

The Ravikumar Lafferty QP paper is a good related paper on this general topic.  One thing that is not immediately clear is why, in the QP paper, the LP performs substantially worse, despite the results in the paper we read.  It could be that the LP or QP used in the Ravikumar paper do not match those in the paper we read.