Towards More Efficient Stochastic Decentralized Learning: Faster Convergence and Sparse Communication

By Zebang Shen, Aryan Mokhtari, Tengfei Zhou, Peilin Zhao, Hui Qian. 2018

60 citations recorded by the source corpus.

Recently, the decentralized optimization problem is attracting growing attention. Most existing methods are deterministic with high per-iteration cost and have a convergence rate quadratically depending on the problem condition number. Besides, the dense communication is necessary to ensure the convergence even if the dataset is sparse. In this paper, we generalize the decentralized optimization problem to a monotone operator root finding problem, and propose a stochastic algorithm named DSBA that (i) converges geometrically with a rate linearly depending on the problem condition number, and (ii) can be implemented using sparse communication only. Additionally, DSBA handles learning problems like AUC-maximization which cannot be tackled efficiently in the decentralized setting. Experiments on convex minimization and AUC-maximization validate the efficiency of our method.

Subfields: Artificial Intelligence, Computer Networks and Communications, Efficiency & Compression, Federated & Distributed Learning

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

1. Ji Liu
2. Hanlin Tang
3. Jianyu Wang
4. Sebastian U. Stich
5. Martin Jaggi
6. Gauri Joshi
7. Tong Zhang
8. Chaoyang He

In Computer Networks and Communications

1. Jianyu Wang
2. Gauri Joshi
3. Hanlin Tang
4. Ji Liu
5. Xiangru Lian
6. Tong Zhang
7. Ce Zhang
8. Anit Kumar Sahu

In Efficiency & Compression

1. Hanlin Tang
2. Chaoyang He
3. Tong Zhang
4. Ji Liu
5. Ce Zhang
6. Xiangru Lian
7. Gauri Joshi
8. Jianyu Wang

In Federated & Distributed Learning

1. Chaoyang He
2. Hanlin Tang
3. Tong Zhang
4. Ji Liu
5. Jianyu Wang
6. Xiangru Lian
7. Ce Zhang
8. Gauri Joshi

Citations in the corpus

• Central Server Free Federated Learning over Single-sided Trust Social Networks (2019, background): “Wu et al. (2017); Shen et al. (2018) shows that the decentralized SGD would converge with a comparable convergence rate to the centralized algorithm with less communication to make large-scale model training feasible.”
• $\texttt{DeepSqueeze}$: Decentralization Meets Error-Compensated Compression (2019, background): “Shen et al. [2018], Wu et al. [2017] shows that the decentralized SGD would converge with a comparable convergence rate to the centralized algorithm with less needed communication to make large-scale model training feasible.”
• MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling (2019, methodology): “The total communication time will be linear in the number of matchings and be bounded by (∆(G) + 1) units, which matches with the communication time model discussed in Section 2 and previous works [31, 6, 28, 18].”
• Distributed Learning over Unreliable Networks (2018, background): “To save the communication cost, some sparse based distributed learning algorithms is proposed (Shen et al., 2018b; Wu et al., 2018; Wen et al., 2017; McMahan et al., 2016; Wang et al., 2016).”
• Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems (2020, methodology): “This minimax optimization formulation includes many machine learning applications such as regularized empirical risk minimization [41, 52], AUC maximization [39, 48], robust optimization [14, 46], adversarial training [16, 17, 40] and reinforcement learning [13, 43].”