Robust Asynchronous Stochastic Gradient-Push: Asymptotically Optimal and Network-Independent Performance for Strongly Convex Functions
arXiv:1811.03982
Abstract
We consider the standard model of distributed optimization of a sum of functions $F(\bz) = \sum_{i=1}^n f_i(\bz)$, where node in a network holds the function $f_i(\bz)$. 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 \begin{enumerate*}[label=(\roman*)] \item node is capable of generating gradients of its function $f_i(\bz)$ corrupted by zero-mean bounded-support additive noise at each step, \item $F(\bz)$ is strongly convex, and \item each $f_i(\bz)$ 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 $f_1(\bz), \ldots, f_n(\bz)$ at each step.
Cited by in corpus (12)
- An improved convergence analysis for decentralized online stochastic non-convex optimization
- A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent
- Fully Asynchronous Distributed Optimization with Linear Convergence in Directed Networks
- Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization
- Local SGD With a Communication Overhead Depending Only on the Number of Workers
- Communication-efficient SGD: From Local SGD to One-Shot Averaging
- Advances in Asynchronous Parallel and Distributed Optimization
- A Survey of Distributed Optimization Methods for Multi-Robot Systems
- Improving the Transient Times for Distributed Stochastic Gradient Methods
- Asymptotic Network Independence in Distributed Stochastic Optimization for Machine Learning
- A general framework for decentralized optimization with first-order methods
- Asymptotic Network Independence and Step-Size for A Distributed Subgradient Method