Distributed optimization of strongly convex functions on directed time-varying graphs
Angelia Nedić, Alex Olshevsky · 2013
We investigate the convergence rate of the recently proposed subgadient-push method for distributed separable optimization over time-varying directed graphs. The algorithm requires no knowledge of either the number of agents or the graph sequence to implement, nor the use of doubly stochastic weights. We show that the algorithm converges at a rate of O(ln t/t) for strongly convex functions. The proportionality constant in the rate estimate depends on some problem parameters, the initial values at the nodes, the speed of the network information diffusion, and the imbalances of influence among the nodes.