Distributed heavy-ball: A generalization and acceleration of first-order methods with gradient tracking

We study distributed optimization to minimize a global objective that is a sum of smooth and strongly-convex local cost functions. Recently, several algorithms over undirected and directed graphs have been proposed that use a gradient tracking method to achieve linear convergence to the global minimizer. However, a connection between these different approaches has been unclear. In this paper, we first show that many of the existing first-order algorithms are in fact related with a simple state transformation, at the heart of which lies the AB algorithm. We then describe textitdistributed heavy-ball, denoted as ABm, i.e., AB with momentum, that combines gradient tracking with a momentum term and uses nonidentical local step-sizes. By simultaneously implementing both row- and column-stochastic weights, ABm removes the conservatism in the related work due to doubly-stochastic weights or eigenvector estimation. ABm thus naturally leads to optimization and average-consensus over both undirected and directed graphs, casting a unifying framework over several well-known consensus algorithms over arbitrary strongly-connected graphs. We show that ABm has a global R-linear rate when the largest step-size is positive and sufficiently small. Following the standard practice in the heavy-ball literature, we numerically show that ABm achieves accelerated convergence especially when the objective function is ill-conditioned.