Low Sample and Communication Complexities in Decentralized Learning: A Triple Hybrid Approach
Low Sample and Communication Complexities in Decentralized Learning: A Triple Hybrid Approach
复制标题
DOI：
10.1109/infocom42981.2021.9488686
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
Xin Zhang;Jia Liu;Zhengyuan Zhu-;E. Bentley
中科院分区：
文献类型：
--
作者：
Xin Zhang;Jia Liu;Zhengyuan Zhu-;E. Bentley
近年来，基于网络共识的分散学习优化算法由于其快速增长的应用而引起了大量关注。然而，大多数现有的分散学习算法无法同时实现低样本和通信复杂性——这是评估分散学习的计算成本和通信成本之间权衡的两个重要指标。为了克服这些限制，在本文中，我们提出了一种三重混合分散随机梯度下降（TH-DSGD）算法，用于有效解决分散学习的非凸网络共识优化问题。我们表明，为了达到ϵ2-stationary解决方案，TH-DSGD的总样本复杂度为O(λ−3)，通信复杂度为O(λ−3)，两者都独立于数据集大小，显著提高了现有作品的样本和通信复杂性。我们用各种学习模型进行了大量的实验来验证我们的理论发现。我们还证明了我们的TH-DSGD算法在网络拓扑变得稀疏时是稳定的，并且在大系统状态下具有更好的收敛性。
Network-consensus-based decentralized learning optimization algorithms have attracted a significant amount of attention in recent years due to their rapidly growing applications. However, most of the existing decentralized learning algorithms could not achieve low sample and communication complexities simultaneously – two important metrics in evaluating the trade-off between computation and communication costs of decentralized learning. To overcome these limitations, in this paper, we propose a triple hybrid decentralized stochastic gradient descent (TH-DSGD) algorithm for efficiently solving non-convex network-consensus optimization problems for decentralized learning. We show that to reach an ϵ2-stationary solution, the total sample complexity of TH-DSGD is O(ϵ−3) and the communication complexity is O(ϵ−3), both of which are independent of dataset sizes and significantly improve the sample and communication complexities of the existing works. We conduct extensive experiments with a variety of learning models to verify our theoretical findings. We also show that our TH-DSGD algorithm is stable as the network topology gets sparse and enjoys better convergence in the large-system regime.