Accelerated consensus via Min-Sum Splitting
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.
In this paper, the authors present an accelerated variant of the Min-Sum message-passing protocol for solving consensus problems in distributed optimization. The authors use the reparametrization techniques proposed in [Ruozzi and Tatikonda, 2013] and establish rates of convergence for the Min-Sum Splitting algorithm for solving consensus problems with quadratic objective functions. The main tool used for the analysis is the construction of an auxiliary linear process that tracks the evolution of the Min-Sum Splitting algorithm.
The main contributions of the paper can be summarized as follows: (i) provide analysis for the Min-Sum splitting algorithm using a new proof technique based on the introduction of an auxiliary process, (ii) design a Min-Sum protocol for consensus problems that achieves better convergence than previously established results, and (iii) show the connection between the proposed method, and lifted Markov chains and multi-step methods in convex optimization.
The motivation and contributions of the paper are clear. The paper is well written and easy to follow, however, it does contain several typos and grammatical mistakes (listed below). The proofs of Propositions 1 and 2, and Theorem 1 appear to be correct.
Typos and Grammatical errors:
- Line 34: “…with theirs neighbors…” -> “…with their neighbors…”
- Line 174: “double-stochastic” -> “doubly-stochastic”
- Line 183: “… can be casted as…” -> “… can be cast as…”
- Line 192: “…class of graph with…” -> “…class of graphs with…”
- Line 197: “…which seems to…” -> “…which seem to…”
- Line 206: “…additional overheads…” -> “…additional overhead…”
- Line 225: “…pugging…” -> “…plugging…”
- Line 238: “…are seen to…” -> “…are able to…”
- Line 240: “…both type of…” -> “…both types of…”
- Line 248: “…also seen to…” -> “…also shown to…”
- Line 279-280: “…to convergence to…” -> “…to converge to…”
- Line 300: “…,which scales like…” -> “…,which scale like…”
- Line 302: “…for the cycle,…” -> “…for cycle graphs,…”
Other minor comments:
- Lines 220 and 221: Do you mean “Lagrangian” and “Lagrange multipliers” instead of “Laplacian” and “Laplace multipliers”?
- The authors present 3 algorithms, and the quantities involved are not always explained or described. For example, what is R_{vw} and r_{vw} in Algorithm 2? Also, in Algorithm 2, the quantities \hat{R}^0 and \hat{r}^0 do not appear to be initialized. Moreover, since the auxiliary linear process is key to the analysis and the central idea of the paper, the authors show clearly state which variables correspond to this in Algorithm 3.
The paper also appears to be missing several references. More specifically:
- Lines 41 and 43: (Sub)gradient methods for consensus optimization. There are several more references that could be included:
-- Bertsekas and Tsitsiklis, Parallel and distributed computation: numerical methods, 1989
-- Sundhar Ram Srinivasan et. al., Incremental stochastic subgradient algorithms for convex optimization, 2009
-- Wei Shi, Extra: An exact first-order algorithm for decentralized consensus optimization, 2015
(and, of course, many more)
- Line 170: “The original literature…”
- Line 229: work by Polyak (Heavy-ball)
- Line 232: work by Nesterov
It would be interesting and useful if the authors could answer/comment and address in the paper the following:
- Although the paper is a theoretical paper, the authors should comment on the practicality of the method, and when such a method should be used as opposed to other distributed methods for consensus optimization. 
- What are the limitations of the Min-Sum Splitting method? 
- What is the intuition behind using the auxiliary process in the Min-Sum Splitting method?
- The results provided in this paper are for consensus problems with quadratic objective functions. Can this framework be extended to solve more general consensus problems that often arise in Machine Learning? 
- The authors should also clearly state why such an approach is of interest in the context of Machine Learning and for the Machine Learning community.
In summary, this paper is a purely theoretical paper in which the authors establish rates of convergence using a new proof technique and show the connections between their method and well-established methods in the literature. Overall, the ideas presented in this paper are interesting, however, the practicality of the method and intuition behind the results are missing, as well as some justification for the  importance of this result for the Machine Learning community.