Asynchronous decentralized optimization in heterogeneous systems

This paper studies a class of asynchronous distributed algorithms for convex optimization where nodes communicate using push-only (feedback-free) broadcast messages, and where nodes do not necessarily perform updates at the same rate. This is especially relevant for implementation in a compute cluster where resources are shared among multiple users and may be simultaneously executing multiple tasks. We consider a distributed variant of Nesterov´s dual averaging algorithm [1], making use of distributed averaging to enable a distributed implementation, and we provide conditions under which the algorithm is guaranteed to converge to the optimal solution. This requires careful scaling of the step size parameters to account for different update rates at different nodes without biasing the solution. The proposed parameter settings assume that nodes have access to readings of a global clock, but otherwise they do not need any global information, including knowledge of their own update rate nor the overall rate at which updates occur across the network. Numerical examples illustrate the performance of the proposed approach and the pitfalls of alternative step-size parameter rules.