Push-Sum Distributed Dual Averaging for convex optimization

TLDR

Recent research has focused on consensus‑based algorithms for distributed optimization in applications such as large‑scale machine learning and wireless sensor networks, and push‑sum offers significant advantages. The paper proposes and proves convergence of Push‑Sum Distributed Dual Averaging, a new algorithm that merges a recent optimization method with a push‑sum consensus protocol. The authors develop Push‑Sum Distributed Dual Averaging and evaluate it through simulations and experiments on a small cluster. The algorithm converges to true average consensus without requiring doubly stochastic protocols or prior knowledge of the stationary distribution, and its simple summation communication semantics enable asynchronous operation and robust analysis under variable communication delays.

Abstract

Recently there has been a significant amount of research on developing consensus based algorithms for distributed optimization motivated by applications that vary from large scale machine learning to wireless sensor networks. This work describes and proves convergence of a new algorithm called Push-Sum Distributed Dual Averaging which combines a recent optimization algorithm [1] with a push-sum consensus protocol [2]. As we discuss, the use of push-sum has significant advantages. Restricting to doubly stochastic consensus protocols is not required and convergence to the true average consensus is guaranteed without knowing the stationary distribution of the update matrix in advance. Furthermore, the communication semantics of just summing the incoming information make this algorithm truly asynchronous and allow a clean analysis when varying intercommunication intervals and communication delays are modelled. We include experiments in simulation and on a small cluster to complement the theoretical analysis.