Accelerated Min-Sum for consensus
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. 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. (joint work with Sekhar Tatikonda.)
Biography:
In the past two years I held a Lecturer position in the Computer Science department at Yale University and a Postdoctoral Associate position at the Yale Institute for Network Science, hosted by Sekhar Tatikonda. I have a Ph.D. in Operations Research and Financial Engineering from Princeton University, where I worked in Applied Probability under the supervision of Ramon van Handel.