2012/11/14 by Tobias Brunsch, Kamiel Cornelissen, Brunsch, Tobias +5
Computer Science · #Bayesian Modeling and Causal Inference #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #Distributed Sensor Networks and Detection Algorithms #FOS: Computer and information sciences #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.1211.3299
openalex publication_date 2012/11/14 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
Belief propagation (BP) is a message-passing heuristic for statistical\ninference in graphical models such as Bayesian networks and Markov random\nfields. BP is used to compute marginal distributions or maximum likelihood\nassignments and has applications in many areas, including machine learning,\nimage processing, and computer vision. However, the theoretical understanding\nof the performance of BP is unsatisfactory.\n Recently, BP has been applied to combinatorial optimization problems. It has\nbeen proved that BP can be used to compute maximum-weight matchings and\nminimum-cost flows for instances with a unique optimum. The number of\niterations needed for this is pseudo-polynomial and hence BP is not efficient\nin general.\n We study belief propagation in the framework of smoothed analysis and prove\nthat with high probability the number of iterations needed to compute\nmaximum-weight matchings and minimum-cost flows is bounded by a polynomial if\nthe weights/costs of the edges are randomly perturbed. To prove our upper\nbounds, we use an isolation lemma by Beier and V "ocking (SIAM J. Comput.\n2006) for matching and generalize an isolation lemma for min-cost flow by\nGamarnik, Shah, and Wei (Operations Research, 2012). We also prove almost\nmatching lower tail bounds for the number of iterations that BP needs to\nconverge.\n