Decentralized Consensus Algorithm with Delayed and Stochastic Gradients

By Benjamin Sirb, Xiaojing Ye. 2016

47 citations recorded by the source corpus.

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.

Subfields: Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

Citations in the corpus

Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms (2018, background): “Decentralized averaging has a long history in the distributed and consensus optimization community (Tsitsik-lis et al., 1986; Nedic & Ozdaglar, 2009; Duchi et al., 2012; Tsianos et al., 2012; Zeng & Yin, 2016; Yuan et al., 2016; Sirb & Ye, 2018).”
COLA: Decentralized Linear Learning (2018, background): “[Sirb and Ye, 2018] proves a O ( K/ ✏ 2 ) rate for stale and stochastic gradients.”
A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent (2019, background): “The work in [38] considered a decentralized algorithm with delayed gradient information, which achieves an O ( 1 √ k ) rate of convergence for general convex functions.”
Communication-Efficient Decentralized Learning with Sparsification and Adaptive Peer Selection (2020, background): “To eliminate the bandwidth problem of the central server, some researchers propose the decentralized distributed training algorithms [6], [25], [44] that training workers only need to communicate with their peers instead of the central server or other n − 1 workers.”
A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates (2018, background): “Other works (such as [21]) focus on a setting where different agents in a network can perform local communication, which is again a different model than ours.”
Asynchronous Incremental Stochastic Dual Descent Algorithm for Network Resource Allocation (2017, methodology): “A consensus-based stochastic algorithm proposed in [25], and utilizes randomly delayed stochastic gradients.”
A Non-Asymptotic Analysis of Network Independence for Distributed Stochastic Gradient Descent (2019, background): “Recently, distributed implementation of stochastic gradient algorithms has received considerable interest [37, 41, 12, 3, 5, 42, 6, 7, 22, 17, 18, 30, 31, 38, 40, 14, 33, 29, 44, 1].”