Robust Asynchronous Stochastic Gradient-Push: Asymptotically Optimal and Network-Independent Performance for Strongly Convex Functions

Abstract

We consider the standard model of distributed optimization of a sum of functions $F(z)=\sum_{i=1}^{n}f_{i}(z)$, where node i in a network holds the function fi(z). We allow for a harsh network model characterized by asynchronous updates, message delays, unpredictable message losses, and directed communication among nodes. In this setting, we analyze a modification of the Gradient-Push method for distributed optimization, assuming that (i) node i is capable of generating gradients of its function fi(z) corrupted by zero-mean bounded-support additive noise at each step, (ii) F(z) is strongly convex, and (iii) each fi(z) has Lipschitz gradients. We show that our proposed method asymptotically performs as well as the best bounds on centralized gradient descent that takes steps in the direction of the sum of the noisy gradients of all the functions f1(z), …, fn(z) at each step.