Message-Passing for Graph-Structured Linear Programs: Proximal Methods and Rounding Schemes

July 21, 2009
Alekh Agarwal | Alekh Agarwal

The problem of computing a maximum a posteriori (MAP) configuration is a central computational challenge associated with Markov random fields. There has been some focus on “tree-based” linear programming (LP) relaxations for the MAP problem. This paper develops a family of super-linearly convergent algorithms for solving these LPs, based on proximal minimization schemes using Bregman divergences. As with standard message passing on graphs, the algorithms are distributed and exploit the underlying graphical structure, and so scale well to large problems. Our algorithms have a double-loop character, with the outer loop corresponding to the proximal sequence, and an inner loop of cyclic Bregman projections used to compute each proximal update. We establish convergence guarantees for our algorithms, and illustrate their performance via some simulations. We also develop two classes of rounding schemes, deterministic and randomized, for obtaining integral configurations from the LP solutions. Our deterministic rounding schemes use a “re-parameterization” property of our algorithms so that when the LP solution is integral, the MAP solution can be obtained even before the LP-solver converges to the optimum. We also propose graph-structured randomized rounding schemes applicable to iterative LP-solving algorithms in general. We analyze the performance of and report simulations comparing these rounding schemes.

Speaker Details

Alekh Agarwal is a 2nd year PhD student in Computer Science Dept. at UC Berkeley, where he does research in learning theory and optimization with Prof. Peter Bartlett and Prof. Martin Wainwright. Alekh is one of the recipients of the MSR Graduate Fellowship for 2009. He got his bachelor’s in computer science from Indian Institute of Technology Bombay, during which he worked in the area of machine learning for web search and ranking. His main research interests are in the area of theoretical machine learning, graphical models and optimization theory.