Asynchronous Decentralized Accelerated Stochastic Gradient Descent

By Guanghui Lan, Yi Zhou. 2018

15 citations recorded by the source corpus.

In this paper, we introduce an asynchronous decentralized accelerated stochastic gradient descent type of algorithm for decentralized stochastic optimization. Considering communication and synchronization costs are the major bottlenecks for decentralized optimization, we attempt to reduce these costs from an algorithmic design aspect, in particular, we are able to reduce the number of agents involved in one round of update via randomization. Our major contribution is to develop a class of accelerated randomized decentralized algorithms for solving general convex composite problems. We establish <inline-formula> <tex-math notation="LaTeX">$\mathcal {O}(1/\epsilon)$ </tex-math></inline-formula> (resp., <inline-formula> <tex-math notation="LaTeX">$\mathcal {O}(1/\sqrt {\epsilon })$ </tex-math></inline-formula>) communication complexity and <inline-formula> <tex-math notation="LaTeX">$\mathcal {O}(1/\epsilon ^{2})$ </tex-math></inline-formula> (resp., <inline-formula> <tex-math notation="LaTeX">$\mathcal {O}(1/\epsilon)$ </tex-math></inline-formula>) sampling complexity for solving general convex (resp., strongly convex) problems. It worths mentioning that our proposing algorithm only sublinear depends on the Lipschitz constant if there is a smooth component presented in the objective function. Moreover, we also conduct some preliminary numerical experiments to demonstrate the advantages of our proposing algorithms over the state-of-the-art synchronous decentralized algorithm.

Subfields: Artificial Intelligence, Computational Mechanics, 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 Artificial Intelligence

In Computational Mechanics

In Computer Networks and Communications

Citations in the corpus

Robust and Communication-Efficient Collaborative Learning (2019, background): “Another line of work proposes asynchronous decentralized SGD, where the workers update their models based on the last iterates received by their neighbors (Recht et al., 2011; Lian et al., 2017b; Lan and Zhou, 2018; Peng et al., 2016; Wu et al., 2017; Dutta et al., 2018).”