Conference item
Accelerated consensus via Min-Sum Splitting
- Abstract:
- We apply the Min-Sum message-passing protocol to solve the consensus problem in distributed optimization. We show that while the ordinary Min-Sum algorithm does not converge, a modified version of it known as Splitting yields convergence to the problem solution. We prove that a proper choice of the tuning parameters allows Min-Sum Splitting to yield subdiffusive accelerated convergence rates, matching the rates obtained by shift-register methods. The acceleration scheme embodied by Min-Sum Splitting for the consensus problem bears similarities with lifted Markov chains techniques and with multi-step first order methods in convex optimization.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 156.4KB, Terms of use)
-
(Preview, Accepted manuscript, pdf, 336.8KB, Terms of use)
-
Authors
- Publisher:
- Curran Associates
- Host title:
- Advances in Neural Information Processing Systems 30: 31st Annual Conference on Neural Information Processing Systems (NIPS 2017)
- Journal:
- NIPS 2017 More from this journal
- Volume:
- 30
- Pages:
- 1375-1385
- Publication date:
- 2018-06-01
- Acceptance date:
- 2017-09-04
- ISSN:
-
1049-5258
- ISBN:
- 9781510860964
- Pubs id:
-
pubs:729367
- UUID:
-
uuid:56db55d5-7953-4b0d-a0c5-3ad435f6a8e7
- Local pid:
-
pubs:729367
- Source identifiers:
-
729367
- Deposit date:
-
2017-11-03
- ARK identifier:
Terms of use
- Copyright holder:
- Tatikonda and Rebeschini and NIPS
- Copyright date:
- 2018
- Notes:
- Copyright © 2017 by the authors and NIPS. This paper was presented at the 31st Annual Conference on Neural Information Processing Systems (NIPS 2017).
If you are the owner of this record, you can report an update to it here: Report update to this record