M. Costantini, N. Liakopoulos, P. Mertikopoulos, and T. Spyropoulos. Working paper.
In decentralized optimization over networks, synchronizing the nodes’ updates incurs significant overhead. Therefore, recent literature has focused on asynchronous algorithms where nodes can activate anytime and contact a single neighbor to complete an iteration. However, most works assume that the neighbor is selected at random based on a fixed probability distribution. Instead, here we introduce an optimization-aware selection rule that chooses the neighbor providing the highest dual cost improvement. This scheme is related to the coordinate descent (CD) method with the Gauss-Southwell (GS) selection rule; in our setting however, only a subset of coordinates is accessible at each iteration, so the existing literature on GS methods does not apply. Therefore, we develop a new analytical framework for smooth and strongly convex functions, and we show that the proposed set-wise GS rule can speed up the convergence in terms of iterations by a factor equal to the size of the largest coordinate set. We analyze extensions of these algorithms that exploit the smoothness constants when known, and otherwise estimate them. We validate our theoretical results through extensive simulations.