Decentralized Consensus Algorithm with Delayed and Stochastic Gradients
arXiv:1604.05649
Abstract
We analyze the convergence of decentralized consensus algorithm with delayed gradient information across the network. The nodes in the network privately hold parts of the objective function and collaboratively solve for the consensus optimal solution of the total objective while they can only communicate with their immediate neighbors. In real-world networks, it is often difficult and sometimes impossible to synchronize the nodes, and therefore they have to use stale gradient information during computations. We show that, as long as the random delays are bounded in expectation and a proper diminishing step size policy is employed, the iterates generated by decentralized gradient descent method converge to a consensual optimal solution. Convergence rates of both objective and consensus are derived. Numerical results on a number of synthetic problems and real-world seismic tomography datasets in decentralized sensor networks are presented to show the performance of the method.
arXiv comment26 pages, 5 figures, accepted by SIAM Journal on Optimization
References in corpus (10)
- On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
- Multi-Agent Distributed Optimization via Inexact Consensus ADMM
- Convex Optimization for Big Data
- Asynchronous Distributed ADMM for Large-Scale Optimization- Part I: Algorithm and Convergence Analysis
- Staleness-aware Async-SGD for Distributed Deep Learning
- DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
- Asynchronous Distributed ADMM for Large-Scale Optimization- Part II: Linear Convergence Analysis and Numerical Performance
- On the O(1/k) Convergence of Asynchronous Distributed Alternating Direction Method of Multipliers
- AdaDelay: Delay Adaptive Distributed Stochastic Convex Optimization
- Decentralized Consensus Optimization with Asynchrony and Delays