Convergence of Min-Sum Message-Passing for Convex Optimization

被引：30

作者：

Moallemi, Ciamac C. ^{[1
]}

Van Roy, Benjamin ^{[2
,3
]}

机构：

[1] Columbia Univ, Grad Sch Business, New York, NY 10027 USA

[2] Stanford Univ, Dept Management Sci & Engn, Stanford, CA 94305 USA

[3] Stanford Univ, Dept Elect Engn, Stanford, CA 94305 USA

来源：

IEEE TRANSACTIONS ON INFORMATION THEORY | 2010年 / 56卷 / 04期

基金：

美国国家科学基金会;

关键词：

Message-passing algorithms; decentralized optimization; convex optimization; BELIEF PROPAGATION; CORRECTNESS; PRODUCT;

D O I：

10.1109/TIT.2010.2040863

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We establish that the min-sum message-passing algorithm and its asynchronous variants converge for a large class of unconstrained convex optimization problems, generalizing existing results for pairwise quadratic optimization problems. The main sufficient condition is that of scaled diagonal dominance. This condition is similar to known sufficient conditions for asynchronous convergence of other decentralized optimization algorithms, such as coordinate descent and gradient descent.

引用

页码：2041 / 2050

页数：10

共 22 条

[1] [Anonymous], 1985, Matrix Analysis
[2] [Anonymous], 1963, Low-Density Parity-Check Codes
[3] [Anonymous], P ALL C COMM CONTR C
[4] [Anonymous], 1995, NONLINEAR PROGRAMMIN
[5] Max-product for maximum weight matching: Convergence, correctness, and LP duality
Bayati, Mobsen
Shah, Devavrat
Sharma, Mayank
[J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 2008, 54 (03) : 1241 - 1251
[6] On the exactness of the cavity method for weighted b-matchings on arbitrary graphs and its relation to linear programs
Bayati, Mohsen
Borgs, Christian
Chayes, Jennifer
Zecchina, Riccardo
[J]. JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT, 2008,
[7] BERROU C, 1993, IEEE INTERNATIONAL CONFERENCE ON COMMUNICATIONS 93 : TECHNICAL PROGRAM, CONFERENCE RECORD, VOLS 1-3, P1064, DOI 10.1109/ICC.1993.397441
[8] Bertsekas D. P., 1997, Parallel and Distributed Computation: Numerical Methods
[9] Boyd S., 2004, CONVEX OPTIMIZATION, VFirst, DOI DOI 10.1017/CBO9780511804441
[10] Survey propagation:: An algorithm for satisfiability
Braunstein, A
Mézard, M
Zecchina, R
[J]. RANDOM STRUCTURES & ALGORITHMS, 2005, 27 (02) : 201 - 226

← 1 2 3 →