Distributed Heavy-Ball: A Generalization and Acceleration of First-Order Methods With Gradient Tracking
Ran Xin, Usman A. Khan · IEEE Transactions on Automatic Control · 2019
We study distributed optimization to minimize a sum of smooth and strongly-convex functions. Recent work on this problem uses gradient tracking to achieve linear convergence to the exact global minimizer. However, a connection among different approaches has been unclear. In this paper, we first show that many of the existing first-order algorithms are related with a simple state transformation, at the heart of which lies a recently introduced algorithm known as AB. We then present distributed heavy-ball, denoted as ABm, that combines AB with a momentum term and uses nonidentical local step-sizes. By simultaneously implementing both rowand 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. We show that ABm has a global R-linear rate when the largest step-size and momentum parameter are positive and sufficiently small. We numerically show that ABm achieves acceleration, particularly when the objective functions are ill-conditioned.