Convergence Rates in Distributed Consensus & Averaging
Thursday, June 5, 2014 - 2:00pm - 3:30pm
We discuss the problem of bounding worst-case convergence rates in distributed consensus and averaging. The presentation will include a self-contained proof of the exponential speedup in worst case convergence speed which comes from choosing the so-called ”Metropolis weights” over the naive equal-neighbors choice in consensus. We will emphasize the link between consensus convergence speed and Markov chain intersection times, and the ability to derive bounds on consensus speed by arguing combinatorially about the latter.