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 <inline formula><tex math notation="LaTeX"\mathcal {AB}/tex math>/inline formula> We then present <italic>distributed heavy ball</italic> denoted as <inline formula><tex math notation="LaTeX"\mathcal {AB}m$/tex math>/inline formula> that combines <inline formula><tex math notation="LaTeX"\mathcal {AB}/tex math>/inline formula> with a momentum term and uses nonidentical local step sizes. By simultaneously implementing both row and column stochastic weights, <inline formula><tex math notation="LaTeX"\mathcal {AB}m$/tex math>/inline formula> removes the conservatism in the related work due to doubly stochastic weights or eigenvector estimation. <inline formula><tex math notation="LaTeX"\mathcal {AB}m$/tex math>/inline formula> thus naturally leads to optimization and average consensus over both undirected and directed graphs. We show that <inline formula><tex math notation="LaTeX"\mathcal {AB}m$/tex math>/inline formula> has a global <inline formula><tex math notation="LaTeX"$R$/tex math>/inline formula> linear rate when the largest step size and momentum parameter are positive and sufficiently small. We numerically show that <inline formula><tex math notation="LaTeX"\mathcal {AB}m$/tex math>/inline formula> achieves acceleration, particularly when the objective functions are ill conditioned.
IEEE Transactions on Automatic Control