Distributed Dual Averaging for Convex Optimization under Communication Delays

TitleDistributed Dual Averaging for Convex Optimization under Communication Delays
Publication TypeConference Proceedings
Year of Publication2012
AuthorsTsianos, K. I., and M. G. Rabbat
Conference NameAmerican Control Conference
Date Published06/2012
Conference LocationMontreal, QC

In this paper we extend and analyze the dis- tributed dual averaging algorithm [1] to handle communication delays and general stochastic consensus protocols. Assuming each network link experiences some fixed bounded delay, we show that distributed dual averaging converges and the error decays at a rate O(T−0.5) where T is the number of iterations. This bound is an improvement over [1] by a logarithmic factor in T for networks of fixed size. Finally, we extend the algorithm to the case of using general non-averaging consensus protocols. We prove that the bias introduced in the optimization can be removed by a simple correction term that depends on the stationary distribution of the consensus matrix.

Refereed DesignationRefereed
acc2012_main.pdf452.39 KB