Convergence of min-sum message-passing for convex optimization

Ciamac Cyrus Moallemi, Benjamin Van RoyIEEE Trans. Information Theory 2010 · OpenReview

Abstract

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.
BibTeX
@article{moallemi2010convergence,
  author = {Ciamac Cyrus Moallemi and Benjamin Van Roy},
  title = {{Convergence of min-sum message-passing for convex optimization}},
  journal = {IEEE Trans. Information Theory},
  year = {2010},
  url = {https://openreview.net/forum?id=zF4_GR6-2oZ},
}

Loading related content...

Figure