Timezone: »

 
Poster
Accelerated consensus via Min-Sum Splitting
Patrick Rebeschini · Sekhar C Tatikonda

Mon Dec 04 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #173
in Posters Mon »

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.

Keywords: Convex Optimization · Belief Propagation
[ Paper]  [ Poster] 

Author Information

Patrick Rebeschini (University of Oxford)
Sekhar C Tatikonda (Yale University)

More from the Same Authors