# Asynchronous decentralized accelerated stochastic gradient descent

**Authors:** Guanghui Lan, Yi Zhou  
**arXiv:** [1809.09258](https://arxiv.org/abs/1809.09258)  
**Date:** 2018-09-24  
**Summary page:** https://www.summarizepaper.com/en/paper/1809.09258v1/

## Key points

- Guanghui Lan and Yi Zhou introduce a novel method for decentralized stochastic optimization
- The proposed method is an asynchronous decentralized accelerated stochastic gradient descent approach
- It achieves $\mathcal{O}(1/\epsilon)$ (resp., $\mathcal{O}(1/\sqrt{\epsilon})$) communication complexity and $\mathcal{O}(1/\epsilon^2)$ (resp., $\mathcal{O}(1/\epsilon)$) sampling complexity for solving general convex (resp., strongly convex) problems.
- Traditional centralized optimization methods require all nodes to communicate with each other and synchronize at every iteration, making it computationally expensive when dealing with large-scale datasets or networks.
- The proposed asynchronous decentralized approach allows each node to operate independently without waiting for others, significantly reducing communication overheads.
- Extensive simulations on various datasets demonstrate the effectiveness of the proposed method compared to existing state-of-the-art algorithms such as distributed stochastic gradient descent and decentralized coordinate descent.
- The proposed method outperforms these algorithms in terms of convergence rate and computational efficiency.
- This paper presents a significant contribution to the field of distributed optimization by proposing an efficient and scalable approach that overcomes the limitations of traditional centralized methods.

## Summary

In their paper titled "Asynchronous Decentralized Accelerated Stochastic Gradient Descent," Guanghui Lan and Yi Zhou introduce a novel method for decentralized stochastic optimization that addresses the communication and synchronization bottlenecks. The authors propose an asynchronous decentralized accelerated stochastic gradient descent approach that achieves $\mathcal{O}(1/\epsilon)$ (resp., $\mathcal{O}(1/\sqrt{\epsilon})$) communication complexity and $\mathcal{O}(1/\epsilon^2)$ (resp., $\mathcal{O}(1/\epsilon)$) sampling complexity for solving general convex (resp., strongly convex) problems. This method is designed to overcome the challenges of traditional centralized optimization methods which require all nodes to communicate with each other and synchronize at every iteration, making it computationally expensive when dealing with large-scale datasets or networks. In contrast, the proposed asynchronous decentralized approach allows each node to operate independently without waiting for others, significantly reducing communication overheads. The authors demonstrate the effectiveness of their method through extensive simulations on various datasets. They compare it against existing state-of-the-art algorithms such as distributed stochastic gradient descent and decentralized coordinate descent. The results show that the proposed method outperforms these algorithms in terms of convergence rate and computational efficiency. Overall, this paper presents a significant contribution to the field of distributed optimization by proposing an efficient and scalable approach that overcomes the limitations of traditional centralized methods. It has practical implications in various domains such as machine learning, data analytics, and network optimization.