Abstract
Gradient sparsification is a promising technique to significantly reduce the communication overhead in decentralized synchronous stochastic gradient descent (S-SGD) algorithms. Yet, many existing gradient sparsification schemes (e.g., Top-k sparsification) have a communication complexity of O(kP ), where k is the number of selected gradients by each worker and P is the number of workers. Recently, the gTop-k sparsification scheme has been proposed to reduce the communication complexity from O(kP ) to O(k log P ), which significantly boosts the system scalability. However, it remains unclear whether the gTop-k sparsification scheme can converge in theory. In this paper, we first provide theoretical proofs on the convergence of the gTop-k scheme for non-convex objective functions under certain analytic assumptions. We then derive the convergence rate of gTop-k S-SGD, which is at the same order as the vanilla minibatch SGD. Finally, we conduct extensive experiments on different machine learning models and data sets to verify the soundness of the assumptions and theoretical results, and discuss the impact of the compression ratio on the convergence performance.
Original language | English |
---|---|
Title of host publication | Proceedings of the 28th International Joint Conference on Artificial Intelligence, IJCAI 2019 |
Editors | Sarit Kraus |
Publisher | International Joint Conferences on Artificial Intelligence |
Pages | 3411-3417 |
Number of pages | 7 |
ISBN (Electronic) | 9780999241141 |
DOIs | |
Publication status | Published - Aug 2019 |
Event | 28th International Joint Conference on Artificial Intelligence, IJCAI 2019 - Macao, China Duration: 10 Aug 2019 → 16 Aug 2019 https://www.ijcai19.org/ https://www.ijcai.org/proceedings/2019/ |
Publication series
Name | IJCAI International Joint Conference on Artificial Intelligence |
---|---|
Volume | 2019-August |
ISSN (Print) | 1045-0823 |
Conference
Conference | 28th International Joint Conference on Artificial Intelligence, IJCAI 2019 |
---|---|
Country/Territory | China |
City | Macao |
Period | 10/08/19 → 16/08/19 |
Internet address |
Scopus Subject Areas
- Artificial Intelligence