Message-passing for graph-structured linear programs: proximal projections, convergence and rounding schemes

ABSTRACT

A large body of past work has focused on the first-order tree-based LP relaxation for the MAP problem in Markov random fields. This paper develops a family of super-linearly convergent LP solvers based on proximal minimization schemes using Bregman divergences that exploit the underlying graphical structure, and so scale well to large problems. All of our algorithms have a double-loop character, with the outer loop corresponding to the proximal sequence, and an inner loop of cyclic Bregman divergences used to compute each proximal update. The inner loop updates are distributed and respect the graph structure, and thus can be cast as message-passing algorithms. We establish various convergence guarantees for our algorithms, illustrate their performance, and also present rounding schemes with provable optimality guarantees.

REFERENCES

• 1: Dimitri P. Bertsekas , John N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods, Athena Scientific, 1997
• 2: Dimitris Bertsimas , John Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997
• 3: Yuri Boykov , Olga Veksler , Ramin Zabih, Fast Approximate Energy Minimization via Graph Cuts, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.11, p.1222-1239, November 2001 [doi>10.1109/34.969114]
• 4: Yair Al Censor , Stavros A. Zenios, Parallel Optimization: Theory, Algorithms and Applications, Oxford University Press, 1997
• 5: C. Chekuri , S. Khanna , J. Naor , L. Zosin, A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem, SIAM Journal on Discrete Mathematics, v.18 n.3, p.608-625, 2005 [doi>10.1137/S0895480101396937]
• 6: Frank Deutsch , Hein Hundal, The rate of convergence for the cyclic projections algorithm I: angles between convex sets, Journal of Approximation Theory, v.142 n.1, p.36-55, September 2006 [doi>10.1016/j.jat.2006.02.005]
• 7: Feldman, J., Karger, D. R., & Wainwright, M. J. (2002). Linear programming-based decoding of turbo-like codes and its relation to iterative approaches. Proc. 40th Annual Allerton Conf. on Communication, Control, and Computing.
• 8: Freeman, W. T., & Weiss, Y. (2001). On the optimality of solutions of the max-product belief propagation algorithm in arbitrary graphs. IEEE Trans. Info. Theory, 47, 736--744.
• 9: Globerson, A., & Jaakkola, T. (2007). Fixing max-product: Convergent message passing algorithms for map lprelaxations. Neural Information Processing Systems (p. To appear). Vancouver, Canada.
• 10: Alfredo N. Iusem , Marc Teboulle, Convergence rate analysis of nonquadratic proximal methods for convex and linear programming, Mathematics of Operations Research, v.20 n.3, p.657-677, Aug. 1995 [doi>10.1287/moor.20.3.657]
• 11: Kolmogorov, V. (2005). Convergent tree-reweighted message-passing for energy minimization. International Workshop on Artificial Intelligence and Statistics.
• 12: Kolmogorov, V., & Wainwright, M. J. (2005). On optimality properties of tree-reweighted message-passing. UAI.
• 13: Komodakis, N., Paragios, N., & Tziritas, G. (2007). MRF optimization via dual decomposition: Message-passing revisited. ICCV. Rio di Janeiro, Brazil.
• 14: M. Pawan Kumar , P. H. S. Torr , A. Zisserman, Solving Markov Random Fields using Second Order Cone Programming Relaxations, Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, p.1045-1052, June 17-22, 2006 [doi>10.1109/CVPR.2006.283]
• 15: Ravikumar, P., Agarwal, A., & Wainwright, M. J. (2008). Message-passing for graph-structured linear programs: Proximal projections, convergence and rounding schemes (Technical Report). UC Berkeley.
• 16: Pradeep Ravikumar , John Lafferty, Quadratic programming relaxations for metric labeling and Markov random field MAP estimation, Proceedings of the 23rd international conference on Machine learning, p.737-744, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143937]
• 17: Solodov, M., & Svaiter, B. (2001). A unified framework for some inexact proximal point algorithms. Numerical Functional Analysis and Optimization, 22, 1013--1035.
• 18: Wainwright, M., Jaakkola, T., & Willsky, A. (2005). Map estimation via agreement on (hyper)trees: Messagepassing and linear-programming approaches. IEEE Transactions on Information Theory, 51, 3697--3717.
• 19: Wainwright, M. J., & Jordan, M. I. (2003). Graphical models, exponential families, and variational inference (Technical Report). UC Berkeley, Department of Statistics, No. 649.
• 20: Weiss, Y., Yanover, C., & Meltzer, T. (2007). Map estimation, linear programming and belief propagation with convex free energies. UAI.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

General Terms:
Algorithms, Design, Theory