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. (Joint work with Sekhar Tatikonda, based on arxiv.org/abs/1706.03807, at NIPS 2017 )

• Speaker: Patrick Rebeschini (Oxford)
• Friday 10 November 2017, 16:00–17:00
• Venue: MR12.
• Series: Statistics; organiser: Quentin Berthet.