Designing Fast Distributed Iterations via Semidefinite Programming
Stephen Boyd (joint work with Lin Xiao)
The general setting we consider involves a process, iteration, or
method in which the computation or communication at each step
is local, determined by a given graph, and
involves some parameters or coefficients that
affect its convergence speed.
Examples include a Markov chain on a graph, where the transition
probabilities affect the mixing rate of the chain;
distributed averaging, where the local weights affect the global speed
of convergence to the average; and
distributed weighted gradient methods for resource allocation,
where the weights affect the speed of convergence to the
optimal allocation.
We show how semidefinite programming can be used to choose the
coefficients or parameters in these methods
to yield fastest (or in some cases, just fast) convergence.
We also show how weights suggested by the celebrated
Metropolis-Hastings algorithm (for fast convergence in
Monte Carlo Markov Chain simulation) transcribe well to other
applications, such as distributed averaging.