Convergence Rate Analysis of MAP Coordinate Minimization Algorithms
Ofer Meshi, Amir Globerson, Tommi Jaakkola · 2012
Finding maximum a posteriori (MAP) assignments in graphical models is an im-portant task in many applications. Since the problem is generally hard, linear pro-gramming (LP) relaxations are often used. Solving these relaxations efficiently is thus an important practical problem. In recent years, several authors have pro-posed message passing updates corresponding to coordinate descent in the dual LP. However, these are generally not guaranteed to converge to a global optimum. One approach to remedy this is to smooth the LP, and perform coordinate descent on the smoothed dual. However, little is known about the convergence rate of this procedure. Here we perform a thorough rate analysis of such schemes and derive primal and dual convergence rates. We also provide a simple dual to primal map-ping that yields feasible primal solutions with a guaranteed rate of convergence. Empirical evaluation supports our theoretical claims and shows that the method is highly competitive with state of the art approaches that yield global optima. 1