Tree-reweighted max-product and linear programming relaxation: Algorithmic connections and some randomized analysis

Martin Wainwright
University of California, Berkeley (UC Berkeley)
Electrical Engineering and Computer Science

An important algorithmic challenge in Markov random fields
(MRF) is efficient computation of the most likely configuration or mode. Although easily solvable for tree-structured graphs, the mode-finding problem for general MRFs is intractable. However, message-passing algorithms, such as the max-product and sum-product algorithm, are widely used to compute approximate solutions. In this talk, we begin by showing how the ordinary max-product algorithm can be very misleading, by converging rapidly to sub-optimal solutions.
We then discuss the class of tree-reweighted max-product algorithms, their associated correctness guarantees, and links to linear programming (LP) relaxation, as well as connections to other distributed algorithms. Finally, we describe dual-certificate methods for establishing optimality of message-passing and/or LP relaxation, and use it to establish high-probability performance guarantees for error-correction based on sparse random graphs.

Based on joint works with Costis Daskalakis, Alex Dimakis, Richard Karp, Vladimir Kolmogorov, Tommi Jaakkola, Alan Willsky.

Presentation (PDF File)

Back to Graph Cuts and Related Discrete or Continuous Optimization Problems