Distributed dual averaging for convex optimization under communication delays
Distributed dual averaging for convex optimization under communication delays
复制标题
DOI：
10.1109/acc.2012.6315289
复制
发表时间：
2012-06
期刊：
影响因子：
--
通讯作者：
Konstantinos I. Tsianos;M. Rabbat
中科院分区：
文献类型：
--
作者：
Konstantinos I. Tsianos;M. Rabbat
在本文中，我们扩展和分析的分布式双平均算法[1]处理通信延迟和一般的随机一致性协议。假设每个网络链路经历一些固定的有界延迟，我们发现，分布式双平均收敛和误差衰减率为O（T-0.5），其中T是迭代次数。对于固定大小的网络，这个界是对[1]的改进，改进了T中的对数因子。最后，我们将算法扩展到使用一般非平均一致性协议的情况。我们证明了在优化中引入的偏差可以通过一个简单的校正来去除，该校正依赖于共识矩阵的平稳分布。
In this paper we extend and analyze the distributed 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 that depends on the stationary distribution of the consensus matrix.