Stochastic Systems Group  

MultiScale Lagrangian Relaxation for Estimation in Discrete and Gaussian Graphical Models
Jason K. Johnson
SSG, MIT
We develop a general framework for MAP estimation in discrete and Gaussian graphical models using Lagrangian relaxation techniques. The basic idea is to reformulate an intractable estimation problem as one defined on a more tractable graph, but subject to additional complicating constraints. Relaxing these constraints gives a tractable dual problem, one defined by a collection of tractable graphs (e.g., small subgraphs or thin graphs such as trees). The popular treereweighted maxproduct (TRMP) method may be seen as an instance of this general approach. We develop a distributed optimization procedure for minimizing the dual function arising in these approaches. For a certain class of Gaussian models, where the objective decomposes as a sum of convex objectives on small subsets of variables, we show that the optimal MAP estimate is recovered and we obtain an upperbound on the variance of each variable. In discrete models, the optimal estimate is recovered only if the method leads to a consistent estimate, one which also satisfies the relaxed constraints. Otherwise, there is a "duality gap", and we consider methods to augment the formulation so as to reduce and possibly eliminate the duality gap.
In addition, we propose a new class of multiscale relaxations that introduce auxiliary variables and associated constraints. The benefits of the multiscale approach include accelerated convergence of our iterative method and reduction of the duality gap in discrete problems.
Joint work with Dmitry Malioutov and Alan Willsky.
Problems with this site should be emailed to jonesb@mit.edu