论文部分内容阅读
随着大数据时代的到来,机器学习模型规模变得越来越大,随机梯度下降(Stochastic Gradient Descent,SGD)算法及其分布式并行变体成为大规模机器学习任务的主要优化算法。虽然现有的分布式随机梯度下降算法在理论上具有优秀的线性加速比性质,但是由于在实践中分布式训练需要引入额外的通信开销,这些算法很难实现真正的线性时间加速比。因此,设计通信高效的分布式并行算法在机器学习的研究中至关重要。本文从两种不同的角度提出改进算法以减小分布式优化中的通信代价。针对大规模深度学习任务,我们提出计算与通信解耦的分布式随机梯度下降(Computation and Communication Decoupled SGD,CoCoD-SGD)算法,通过并行执行计算和通信以减小通信开销。我们从理论上证明了所提出的算法在同构和异构两种计算环境中都具有线性加速比。另外,相比于已有的分布式优化算法,所提出的算法具有更低的通信开销和更高的时间加速比。具体来说,当使用N个计算设备协同地进行T次迭代,CoCoD-SGD的通信复杂度为O(N3/4T3/4),与目前最优的算法局部随机梯度下降(Local-SGD)持平,但由于CoCoD-SGD可以并行地执行计算和通信,所以达到了更优的时间加速比。在深度神经网络上的实验结果验证了 CoCoD-SGD算法的优越性。从通信复杂度的角度,已有的关于Local-SGD的研究采用固定的或者自适应的通信周期,并证明了当机器间的数据分布相同(ⅡD)或不同(Non-ⅡD)时,Local-SGD的通信复杂度分别是O(N3/2T1/2)和O(N3/4T3/4)。在本文中,通过逐阶段提升通信周期并减小学习率,我们提出阶段性局部随机梯度下降算法(Stagewise Local SGD,STL-SGD)。我们证明了 STL-SGD能够保持与小批量随机梯度下降(mini-batch SGD)相同的收敛性和线性加速比。另外,得益于递增的通信周期,如果目标函数是凸函数或者其满足Polyak-Lojasiewicz条件,对于ⅡD情景和Non-ⅡD情景,STL-SGD的通信复杂度分别是O(N log T)和O(N1/2T1/2),相对于Local-SGD有明显提升。在凸问题和非凸问题上的对比实验证明了STL-SGD算法卓越的实践性能。