A Distributed Asynchronous Generalized Momentum Algorithm Without Delay Bounds

Abstract

Asynchronous optimization algorithms often require delay bounds to prove their convergence, though these bounds can be difficult to obtain in practice. Therefore, we introduce a novel distributed generalized momentum algorithm that provides fast convergence and allows arbitrary finite delays. It subsumes Nesterov's accelerated gradient algorithm and the heavy ball algorithm, among others. We first develop conditions on the parameters of the algorithm that ensure asymptotic convergence. Then we show its convergence rate is linear in a function of the number of computations and communications that processors perform (in a way that we make precise). Simulations compare this algorithm to gradient descent, heavy ball, and Nesterov's accelerated gradient algorithm with a text classification problem on the 20 newsgroups dataset. Across a range of scenarios with unbounded delays, the generalized momentum algorithm converges with at least 36% fewer iterations than gradient descent, 28% fewer iterations than the heavy ball algorithm, and 16% fewer iterations than Nesterov's accelerated gradient algorithm.

12 pages, 1 figure