Distributed Heavy-Ball: A Generalization and Acceleration of First-Order Methods With Gradient Tracking

摘要

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 AB, that combines AB with a momentum term and uses nonidentical local step-sizes. By simultaneously implementing both row- and column-stochastic weights, AB removes the conservatism in the related work due to doubly stochastic weights or eigenvector estimation. AB thus naturally leads to optimization and average consensus over both undirected and directed graphs. We show that AB has a global R-linear rate when the largest step-size and momentum parameter are positive and sufficiently small. We numerically show that AB achieves acceleration, particularly when the objective functions are ill-conditioned.