GT-STORM: Taming Sample, Communication, and Memory Complexities in Decentralized Non-Convex Learning
GT-STORM: Taming Sample, Communication, and Memory Complexities in Decentralized Non-Convex Learning
复制标题
DOI：
10.1145/3466772.3467056
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
Xin Zhang;Jia Liu;Zhengyuan Zhu-;E. Bentley
中科院分区：
文献类型：
--
作者：
Xin Zhang;Jia Liu;Zhengyuan Zhu-;E. Bentley
由于分散非凸优化在系统健壮性、数据保密性和实现简单性等方面的优势，近年来在机器学习领域受到越来越多的关注。然而，设计分散优化算法的三个基本挑战是如何降低采样、通信和存储的复杂性。本文提出了一种基于梯度跟踪的随机递归动量(GT-STORM)算法，用于有效地求解非凸优化问题。我们证明了要达到ϵ2平稳解，该算法的样本评估总次数为？(M1/2ϵ-3)，通信轮数为？(M1/2ϵ-3)，从而改善了现有分散随机梯度算法样本评估和通信的O(ϵ-4)代价。我们用各种学习模型进行了广泛的实验，包括非凸逻辑回归和卷积神经网络，以验证我们的理论结果。总而言之，我们的结果有助于促进分散网络优化理论和算法的发展。
Decentralized nonconvex optimization has received increasing attention in recent years in machine learning due to its advantages in system robustness, data privacy, and implementation simplicity. However, three fundamental challenges in designing decentralized optimization algorithms are how to reduce their sample, communication, and memory complexities. In this paper, we propose a gradient-tracking-based stochastic recursive momentum (GT-STORM) algorithm for efficiently solving nonconvex optimization problems. We show that to reach an ϵ2-stationary solution, the total number of sample evaluations of our algorithm is Õ(m1/2ϵ-3) and the number of communication rounds is Õ(m1/2ϵ-3), which improve the O(ϵ-4) costs of sample evaluations and communications for the existing decentralized stochastic gradient algorithms. We conduct extensive experiments with a variety of learning models, including non-convex logistical regression and convolutional neural networks, to verify our theoretical findings. Collectively, our results contribute to the state of the art of theories and algorithms for decentralized network optimization.