Convergence Rates in Distributed Consensus & Averaging

Thursday, June 5, 2014 - 2:00pm - 3:30pm
Lind 305
Alex Olshevsky (University of Illinois at Urbana-Champaign)
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.
MSC Code: