大神详解！去心量子化的SGD算法

随机梯度下降法是现代机器学习算法的基础，大量的机器学习模型都是依赖随机梯度下降法进行训练。现阶段主流的并行随机梯度下降法都是使用参数服务器进行实现。参数服务器自从2012年由distbrief介绍以来经过多年发展已近趋向成熟，但是也凸显出很多问题：1.网络热点明显，2.网络负载较大。为了解决上述问题去心化和量子化的SGD算法近年来得到了关注并独立发展。本次分享将介绍张潼老师2018年4月挂在arxiv上的论文，这篇论文介绍了两种结合了去心化和量子化的并行SGD算法，通过实验和理论证明了他们的有效性。

现阶段主流的分布式机器学习训练平台是参数服务器。参数服务器的工作模式如下图。

这种机器学习训练模型是Delay-SGD算法[1]的工程实现。Delay-SGD算法是现阶段最有效的并行随机最优化算法。

但是随着机器学习的发展，机器学习的模型越来越大，越来越稠密，对于网络和系统并行度的需求也越来越高。随着worker的增多和模型的增大，参数服务器的缺陷也逐渐显露出来。Worker增多会导致提交延迟梯度的延迟增大，有论文认为当worker增多到一定程度，算法收敛效率会急剧下降。机器学习模型较大时，有些网络负载将成为瓶颈。同时作为一个有心的分布式平台，服务器端将会成为网络热点，进一步导致网络拥塞，影响整体的训练效率。

针对上述的两个问题，现阶段也有一些算法或者工程上的解决方法。针对worker较多的问题，有些论文通过“蒸馏学习”的方法进行求解，微软团队也针对此研究了DC-SGD算法解决延迟过大的问题。 针对网络负载较大的问题，在算法上有较多团队使用了“量子化”的方式，将原始数据的每个值都分类1,0，-1三个状态（当然可以更多状态），用这种方法进行压缩之后网络传输。本质上“量子化”的过程是一个引入截断误差的过程。在工程上，现阶段的主要方法是分割模型，将模型的不同部分放到不同的服务器上，从而降低了网络热点，但工程上的方法是不降低网络的负载的。

针对上述问题，学术界也有人想改变使用delay-SGD算法来改变现状。典型的是使用去心化SGD算法来解决问题。一种常用的去心化SGD算法如下：

这个算法中，每个节点都存有一个模型。每个迭代步，本地节点都拉取相邻节点的模型进行平均，之后选取样例进行随机梯度的下降。最终将所有节点进行平均求出最终的模型。

上述算法很好地解决了有心带来的问题，如worker数量的拓展性问题和热节点的问题。但是当机器学习模型很大很稠密的时候，对网络的负担依旧会很大。因此对模型进行“量子化”也就成为了自然的想法。

但是实践证明量子化并不能很好地实现在上述的去心SGD算法中。因为量子化带来的阶段误差会在网络传输中累积，没有办法被随机性消除。基于这个问题，Hanlin Tang等人[2]在18年3月在axriv上放了一篇如何在上述去心SGD算法中引入量子化的方法。本文中提出了两个算法，分别是ECD-PSGD和DCD-PSGD。

这两种算法通过压缩本地模型的增量，并将压缩后的增量传输给邻居节点更新邻居节点的模型完成整个迭代步。不同的是两个方法压缩增量的方式并不相同。

这两种方法的理论上限都显示，这两种方法可以使得目标函数值快速下降。而且随着节点数目的增多，因为数据集带来的模型方差都会快速下降，从而达到可拓展的目的。

这篇论文用这两种算法和传统有心算法做了对比，同时相同算法下对不同压缩的精度进行测试。效果如下。

从图中跟我们可以看出，在截断精度逐步降低的情况下，从没代的角度看，损失函数收敛的速度没有显著差异。但是因为高截断带来网络负载上的受益，从时间角度看，收敛速度收缩的非常显著。

基于本文的读者的目的和证明难度，这里不介绍算法证明的全部细节。仅仅用语言介绍一下证明的出发点和算法设计的出发点。证明的出发点在于损失函数的利普希茨连续性假设，通过多项式展开损失函数探索证明的后续工作。通过展开损失函数和适当的放缩，可以得到下面的上限，即文中的lemma 8：

Lemma 8是整个证明的起始点和支点。所有基于最开始我们介绍的分布式去心SGD算法的工作都要依赖于Lemma 8作为基石。Lemma8中左边第一项是证明极值需要的一项，左边第二项因为可以调整步长约去并不影响不等号方向，所以并不重要，右边第一项，第二项正好组成了裂项求和的基本形式，右边最后一项是由分布式去心SGD算法所决定的。因此再设计算法的时候，应该着重设计设计算法使得右边第三项和第四项具有一个上限。基于此，作者设计出了两种算法，并使用Cesaro和完成整个证明。

[1]Langford J, Smola A J, Zinkevich M. Slow learners are fast[C]// International Conference on Neural Information Processing Systems. Curran Associates Inc. 2009:2331-2339.

[2]Tang H, Zhang C, Gan S, et al. Decentralization Meets Quantization[J]. 2018.

- END -

关注智铀科技公众号