Linear Convergence of Asynchronous Gradient Push Algorithm for Distributed Optimization

This article focuses on multiagent distributed asynchronous optimization over directed networks where each agent can only access its individual local function, and the aggregate aim is to minimize the cumulative sum of all local functions. Considering the asynchrony among the agents, we develop an algorithm in which agents compute and communicate individually, without any form of synchronized coordination. Agents perform their local updates by local communication with their immediate neighbors, and this may involve the use of stale information. Since asynchrony naturally leads to latency or packet loss, an asynchronous robust gradient tracking mechanism is developed to guarantee estimating the average of agents’ gradients precisely. Moreover, it employs uncoordinated step-sizes which are more flexible and general than constant or decaying step-size. When the global objective is strongly convex and the local objectives have Lipschitz-continuous gradients, we prove that each agent executing the asynchronous algorithm linearly converges to the consensus optimal point at an <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathcal {O}(\lambda ^{k})$ </tex-math></inline-formula> rate, where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\lambda \in (0,1)$ </tex-math></inline-formula> is convergence factor and k represents the iteration number, with a step satisfying a tight explicit upper bound. Numerical experiments demonstrate that our algorithm has better advantages over the state-of-the-art asynchronous algorithms.