《分布式机器学习》-刘铁岩：全书汇总_刘铁岩 分布式机器学习

摘要

1 背景

近十年来，互联网技术的发展以及4G等通信技术的提升使得我们进入了一个大数据时代。而要处理这些庞大复杂的数据，又需要庞大的模型。例如：ImageNet数据集包含1400万幅图像，涵盖了2万多个类别【1】。百度的Deep Speech 2系统使用了11940小时的语音数据以及超过200万句表述来训练英语的语音识别系统【2】。WMT2014的英法训练数据集包涵了约3600万的英法语句对【3】。3000多万个残局被Deep-Mind用来训练AlphaGo围棋对战系统【4】。当然还有比上述数据集更加庞大复杂的数据。这些种类繁复，样本量大的数据集为机器学习技术的发展提供了最原始的动力，特别以深度学习为例。但是大数据也有大数据的弊端，当数据庞大到单机无法储存运算的时候，大数据反而成为一个挑战。另外，要充分利用到上述的数据，就需要用到更加复杂的模型，不然用庞大的数据集来训练简单的模型，很容易造成模型的欠拟合。在大模型的训练数据的基础下，涌现出了很多大规模的机器学习模型。比如2015年微软研究院开发出来拥有200亿个参数的LightLDA主题模型【5】。2019年谷歌最新研究提出一种用于大规模多语言的大规模神经翻译方法，针对 100 + 种语言，超过 500 亿参数训练一个 多语言神经机器翻译模型【6】。在自然语言处理中，当次表增加到成千上万时，上千亿个参数数的模型也是可能的。但是这就引出了另外一个问题，计算复杂度高，在单机上训练所需要的的时间可能是难易接受的。另外，单是模型的存储，在单机上可能也不够。
大数据和大模型是相辅相成的，共同推动着人工智能的发展。但不可避免得我们也面临着上述的挑战。这里就包括本文中点要阐述的大规模计算机集群的广泛使用，即分布式的机器学习。
近年来随着人工智能的飞速发展，使得亚马逊AWS、谷歌Google Cloud以及阿里云等云计算平台得到了巨大发展。使用云计算来训练机器学习模型成为一件常见的事情。同时很多大公司或是学术机构也都搭建自己的GPU集群。目前很多的人工智能产品或是研究背后，往往都是成百上千块的GPU集群上并行训练的结果。
CPU集群为基于大数据、大模型的人工智能奠定了夯实的基础，然而尽管硬件达标了，没有相应的“软件”支持也是不可行的。也就是如何划分数据、模型；如何调配计算资源；如何整合分布训练的结果这三大主要问题。近年来也有越来越多的研究者开始深入研究分布式的机器学习技术。针对这三个问题分布式机器学习大致有三种方式。1、针对计算量太大的问题，一般采用基于共享内存的多线程或多机并行运算来解决。2、对于训练数据太多的情形，往往会对数据进行划分，然后分配到每个工作节点上进行训练，并且按照一定的规则通信，最后进行整合；3、对于模型多大的情形，通常会对模型进行划分并分配到不同的节点上去进行训练。因为不同模型之间依存关系往往高于不同数据，比如一个模块的输出是另一个模块的输入，所以模型划分往往意味着更多的节点通信。但是要注意的是，现实往往更加复杂，可能会是同时面临上述的三个问题，这就需要结合不同方式。
上述的三种情形都可以简化为三个部分：1、模型与数据的划分；2、单机上模型的训练；3、模型与数据的聚合。可以用下图进行描述。

本文将从上述框架为脉络对分布是机器学习进行综述，并介绍着重分布式的优化算法和算法分析。

2 数据划分与模型并行

在简介部分我们也已经认识到了大数据、大模型的挑战给我们带来了三个挑战，包括算力、数据量过大、以及模型过大。针对这三个挑战衍生了三种不同的并行模式。包括：计算并行模式、数据并行模式以及模型并行模式。首先对三种并行模式之间的关系和适用情况通过一个表格进行介绍。

上表详细地总结了不同的并行模式。可以看出计算并行适用于无需数据划分和模型划分的情况。单一的数据并行主要要对样本进行划分（也可以对数据的维度进行划分）。对于模型划分，神经网络和线性模型有不同的划分方式。2.1小结剩下部分会对此进行详细介绍。

2.1 计算并行模式

针对计算量太大的问题，一般采用基于共享内存的多线程或多机并行运算来解决。这样每个工作节点都具有对数据的完全访问权，这就相当于单机上的多线程环境。对于此类系统，我们只需要把注意力集中在如何并行地执行相应的优化算法上。这里以随机梯度下降法SGD为例来描述内存共享情况下如何同步并行。对SGD的详细介绍可以在后面看到。并行随机梯度下降法（SSGD）算法流程如下：

可以看到SSGD和SGD的区别很小，上述的算法就等价于K-batch的SGD。用k个数据的平均梯度来代替梯度的期望。唯一不同之处在于在k个数据梯度的计算是并行的。那么上述算法的收敛性和收敛速度如何呢？收敛性和K的选取相关的，收敛速度和条件数相关的，这里不做详细介绍。

2.2 数据并行模式

对于训练数据太多的情形，往往会对数据进行划分，然后分配到每个工作节点上进行训练。数据样本划分和数据维度划分是两种常见的数据划分方式。其中样本划分又分为随机采样和置乱切分两种。随机采样，即有放回地随机抽样，这样可以保证每一个单机上的数据都是独立同分布，缺点是耗时，其计算复杂度为O(n)，并且对占比很小的样本不容易抽样到。置换切分，即对原始数据进行随机分组。一般在实践中也采用这种方法，在操作上，会对样本随机置乱，然后再划分为K等份。其计算复杂度为O(log n)。这样得到的小样本是不独立分布的，但是划分速度快，且弥补了随机采样小样本不容易抽样到的缺点。当划分到单机的数据执行完一次之后，会有两种对数据进行再处理的方法：一种是对所有数据进行置乱切分，另一种只对单机上的数据再次进行局部的置乱切分。
带有样本划分的分布式随机梯度下降法的算法流程如下，

对于上述算法的收敛性分析与基于miniBatch-SGD的类似，这里对其收敛速度进行讨论。
假定目标函数都是光滑的，带有随机采样样本划分的并行随机梯度下降法的收敛速度如下：$$O(\frac{1}{\sqrt{nS}}+\frac{bK}{nS})$$带有全局置换切分的并行随机梯度下降法的收敛速度如下：$$O(\frac{1}{\sqrt{nS}}+\frac{bK}{nS}+\frac{\log n}{n})$$带有局部置换切分的并行随机梯度下降法的收敛速度如下：$$O(\frac{1}{\sqrt{nS}}+\frac{bK}{nS}+\frac{K\log n}{n})$$
其中n为样本数，S为轮数，b为小批量规模。
可以看到从随机采样到全局置换切分，再到局部置换切分，收敛速率依次减小，这是因为这几种方法采样得到的样本的分布相比于样本原分布越来越偏离。
一般数据划分要考虑两个因素，一个是数据量和数据维度和本地内存的相对大小，另一个是优化方法的特点。样本划分适用于随机抽取样本的方法，如随机梯度下降法。维度划分适用于随机抽取维度的方法，如随机坐标下降法。维度划分也是数据划分的一个重要方向。
一般情况下的损失函数是和数据的所有维度都密切相关的，比如说神经网络。但是同样存在各个维度之间不耦合的方法，包括决策树的方法以及线性模型。对于这两类方法，可以通过不同维度的划分进而划分数据。

2.3 模型并行模式

对于模型很大以至于不能储存在工作节点的本地内存中的情形，通常会对模型进行划分并分配到不同的节点上去进行训练。对具有变量可分性的线性模型和变量不同维度之间相关性很高的非线性模型，模型的划分并行方式存在较大的差异。

2.3.1 线性模型

在线性模型中，包括线性回归、logistic回归等等，参数往往是与数据的维度一一对应的。所以我们就可以将数据和模型按照维度划分，分配到不同的工作节点使用坐标下降法。
本文在这里介绍2016年发表的名为Hydra（HYbriD cooRdinAte descent）的随机坐标下降法。这里之所以起这个名字是因为这里的并行一方面体现在不同节点之间的并行，另一方面节点内部也是利用多线程并行。该算法是要解决下述的问题：$$\underset{x\in R^d}{\min }L(x):=f(x)+R(x)$$这里的f是一个光滑的凸的损失函数，R是一个凸的但不一定光滑的正则项（例如L1范数）。
关于损失函数$f$，我们会假设对于所有$x，h\in {\mathbb{R}}^d$都存在一个正定举证$M\in {\mathbb{R}}^{d\times d}$，满足$$f(x+h)<f(x)+(\nabla f(x){)}^{T}h+\frac{1}{2}{h}^{T}Mh$$此处的$M=A^{T}A$，A是一个n×d的矩阵。
很多线性的问题都符合上述的假设。上述的$f(x)$可以写成l损失函数的形式形式：$$f(x)=\sum _{j=1}^{n}l(x,A_{j:},y^j)$$其中矩阵A就是n个d维特征的样本，$l$是对于一个样本的损失函数。可以是很多的形式，包括平方损失（SL），logistic损失（LL）以及平方Hinge损失（HL）。其中SL以及HL，其Hession矩阵都是$M=A^{T}A$，而对于LL，其Hession矩阵都是$M=\frac{1}{4}{A}^{T}A$。
关于正则项R，我们假设R是不同维度可分的。常见的L1和L2范数都是维度可分的，即$$R(x)=\sum _{i=1}^d{R}_i(x^i)$$对于满足上述假设的问题我们可以采用Hydra，通过对模型进行划分来分布式地优化。Hydra的算法流程如下：

算法中的第七步是模型参数更新得主要步骤，这里采用了二阶的方法。通常情况下，第七步当中的更新公式是存在闭式解的。在收敛性和收敛速度分析中，如果正则化经验风险是强凸的，那么上述算法具有线性收敛速度。

2.3.2 神经网络

近年来随着深度学习的发展，人们使用神经网络的规模越来越大，这样就遇到了大模型的问题。但是又由于神经网络具有很强的非线性，参数之间的依赖关系比较重，这就使得我们不能按照维度来对数据和模型进行划分。但是从另一方面来看，神经网络的层次化结构为企带来了一定的便利性。我们可以横向按照层来划分模型。可以纵向跨层来对模型进行划分，也可以利用神经网络的参数冗余性随机划分。本小节以全连接神经网络为例进行了介绍，但其并不失一般性。
1、横向按层划分
顾名思义，横向按层划分就是把一个层或多个层的运算划分给单个工作节点。以四层神经网络为例，其按层划分的示意图如下所示：

以工作节点1为例，节点1主要执行输入层到第一个隐藏层边上的权重的迭代更新，在节点1中存储了输入层的数据，隐藏层激活函数的值以及边上的参数值，以及反向传播所需的误差传播图。
神经网络之间的前向传播和后向传播依靠节点之间的通讯完成。比如说节点1将计算更新的隐藏层1的激活值发送给节点2，更新节点2中存储的隐藏层1的激活值，继续向下传播。反向传播亦然。
神经网络的横向按层划分模型大的并行运算算法如下：

因为横向按层划分的并行方式，需要相互等待借用相邻工作节点的信息来完成前传和后传。为了提高工作效率，一般会让这些节点按照编号一次开始工作，形成流水线。
2、纵向跨层划分
对于层数不多，但是单层的神经元很多的情况，我们可以进行纵向的跨层划分。我们先来考虑一个输入维度4，输出维度1，两个包含4个神经元的隐藏层的全连接神经网络。对其纵向跨层划分如下如所示：

结合上面两个工作节点时的纵向划分，我们可以得到以下的一般性描述。将K个工作节点上存储的信息记作 { G 1 , G 2 , … , G k } \{G_{1},G_{2},\dots,G_{k}\} {G1​,G2​,…,Gk​}，这包含了隐含层神经元、输入输出层，及其在全网络中的所有连边。记$G_k=(G_k^0,E_k)$,其中$G_k^0$表示子模型内部连边的权重以及激活函数值和误差传播值。$E_k$为该子模型和其他子模型之间的连边权重。记其他子模型的信息为$V_k$。工作节点在更新子模型的过程中，需要通信获取$V_k$中所有神经元的激活函数值和误差传播值。则神经网络的纵向跨层划分模型并行算法如下：

如果网络的层数很多，并且每层的神经元数目也很多，则需要吧横向按层划分和纵向跨层划分结合起来。也可以使用下面要讲的模型随机并行。

3、模型随机并行
由于纵向和横向划分的通信代价都比较打，研究人员们提出了针对大规模神经网络的模型随机划分方式【Slim-DP: A Multi-Agent System for Communication-Efficient Distributed Deep Learning】。该方法的基本思想是：神经网络有一定的冗余性，可以找得到一个规模小很多的子网络（称为骨架网络），其效果与原网络差不多。所以可以先选出骨架网络存储在各个工作节点之中。然后出去骨架网络之外，每个节点随机选择一些其他网络存储。骨架网络周期性地一句新的网络重新选取，而用于探索的节点也会每次随机选取。其示意图如下：

可以看出模型随机划分的关键在于选取骨架网络。可以根据一点网络研究中的指标，比如边的权重等。这方面问题在模型压缩和删减领域有深入的研究。但是在训练开始之初，选取的骨架网络会比较不稳定，所以要更多地进行随机探索。等到训练后期，骨架网络就会比较稳定。神经网络的随机并行算法如下：

相比于纵向跨层划分，模型随机并行的整体训练速度要快，尤其是在复杂的大模型下，这主要是因为模型随机并行避免了很多通行。

3 通信机制

分布式机器学习中，通信是必不可少的环节。不过，受限于分布式系统间的网络传输速率，通信常常成为分布式机器学习系统的瓶颈。如果某个任务计算和通信的时间占比为1:1，那么根据阿姆达尔定律，无论使用多少台机器并行运算，加速比都不会超过两倍。所以压缩通信时间是分布式机器学习中一个重要的问题。但是机器学习任务往往是迭代优化的，意味着要进行很多次通信。因而我们便需要一个高效的通信机制来解决通信时间的问题。在本节将从通信的内容，及传输什么信息；通信的拓扑结构，即哪些节点之间互相通信；通信的步调，即在各个节点通信时，如何处理速度差异；通信的频率，也就是如何从通信次数和单次时间上减少通信，这四个方面介绍分布式机器学习系统的通信机制。

3.1 通信的内容

通信的内容是和并行方式相关的。上一节介绍的无论是数据划分的并行模式还是模型划分的并行方式，都需要进行通信，并且通信的内容也各有不同。但是通信内容大体上可以分为参数或者参数的更新和计算中间结果。
以带有样本划分的分布式随机梯度下降法的算法（2.2节）为例，通信的内容是模型的参数或者是参数的更新。因为随着算法越来越收敛，参数以及参数的更新就会变得很稀疏，这会使得通信的内容变少很多。至于为什么参数以及参数的更新就会变得很稀疏会使得通信内容变少，在通信的频率中会有介绍。在以模型划分的并行模式中，计算的中间结果会成为通信的内容。以神经网络的横向按层划分为例，在模型优化过程中，各个子模型的激活值还有反向传播时的误差值是通信的主要内容。
在实践中，还存在其他情况，在基于数据交互的数据并行机器学习中，各个工作节点会将本地数据中的最重要的那一部分进行通信，比如支持向量机中的支持向量，Boosting算法中权重最大的样本等。此外，还可以通信获取样本的预测值，这在集成学习中有较多使用。总之，通信的内容会随着并行模式的差异以及机器学习任务的不同而变化。

3.2 通信的拓扑结构

通信的拓扑结构是指分布式机器学习系统中各个工作节点之间的连接方式。通信拓扑结构的演化与分布式机器学习的发展历史有关。早起当人们用于训练的数据量还不够大，训练模型还不复杂的时候，分布式机器学习常常利用已有的分布式计算框架实现通信，如消息通信借口（MPI）或者MapReduce计算框架。这类通用的计算框架部署简单，但也有本身的缺点，比如MPI方式只适合于同步计算。随着数据变多，模型变得复杂，基于参数服务器的二部图的网络拓扑结构被广泛地使用。再后来随着深度学习的普及，机器学习系统将计算和通信统一抽象为一个数据图模型，通信可以在两个任意相连的图节点之间产生。

3.2.1、基于迭代式MapReduce的通信拓扑

MapReduce将程序抽象为两个主要操作：Map操作完成数据分发和并行处理，Reduce操作完成数据的全局同步和归约。当我们把MapReduce应用到分布式机器学习中，Map操作定了数据分发以及在本地工作节点上的计算，而Reduce操作是指全局参数的聚合过程。利用迭代是MapReduce的操作，可以实现典型的数据并行模式下的同步分布式机器学习算法，比如带有样本划分的分布式随机梯度下降法的算法（2.1.2节）。MapReduce的示意图如下，整个计算流程就是不断迭代重复Map、shuffle、Reduce的操作。

3.2.2、基于参数服务器的通信拓扑

前面提到的迭代式MapReduce的通信拓扑，只支持同步算法，也就是说，其计算效率往往受到系统中最慢的节点的限制。当其中有一个节点出现故障，会使得整个系统被迫暂停。另外，对于模型划分的并行模式，迭代式MapReduce也无法适用。随着数据越来越多，模型越来越复杂，更多地异步算法被提出，基于参数服务器的分布式机器学习框架被提出。
如下图所示，

在基于参数服务器的通信拓扑中，不同的工作节点之间不互相通信，所有工作节点至于参数服务器节点通信。各个工作节点负责处理本地的训练任务，并与参数服务器通信，从其获得最新的全局参数或者将本地训练得到的新的参数发送给参数服务器。从逻辑上看，参数服务器采用了二部图的通信拓扑结构。在基于参数服务器的分布式机器学习框架中，机器学习的步调可以是同步的，也可以是异步的。目前该框架得到了产业界和学术界的广泛使用。

3.2.3、基于数据流的通信拓扑

近年来，随着深度学习的发展，研究者们提出了基于数据流的分布式机器学习系统。在这种系统中，计算被描述为一个有向无环的数据流图。图中的每个节点进行数据处理或者计算，每条边代表数据的流动。该模式下的工作节点示意图如下：

主要有两个通信通道：控制消息流和计算数据流。其中计算数据流主要接受模型训练时所需要的数据，模型参数等，控制消息流控制需要接受什么数据，校正数据的完整性等。数据流图其实除了应用在分布式机器学习领域，在其它领域也有广泛使用。并且上述的迭代式MapReduce和基于参数服务器的通信拓扑，都可以使用数据流图表示。

3.3 通信的步调

控制各个节点的通信步调，是为了更好地进行不同节点间的协调配合。在前面内容中，我们已经经常提到同步异步了，这就是指的分布式机器学习的通信步调。其中同步是指要求所有的工作节点的步调是相同的。采用同步，基本可以保证分布式算法和单机算法的等价性，从而利于算法的分析调试。但是同步会使得各个节点之间相互等待，造成计算资源闲置。异步是指各个机器按照积极的步调训练，无需彼此等待，从而最大化计算资源的利用率。但是因为不容工作节点之间模型的不一致，会导致延迟的出现。所谓延迟是指，因为各个工作节点之间没有全局同步，所以步调可能差距很大。例如某个工作节点速度很快，当其在全局模型的基础上训练了100轮之后，而另外一个工作节点速度慢，才进行了一轮。当后者把一个很陈旧的局部模型写入服务器是，很可能会减慢全局的收敛速度。
在这两种极端的通信步调之外，还存在一种折中的方法，试图平衡同步异步的优缺点。下面介绍一种比较经典的方法【9】——延时同步并行（SSP）。它的核心思想是控制最快和最慢节点之间相差的迭代次数不超过预设的阈值。在SSP的逻辑控制下，只要各个工作节点的迭代次数不超过预设的阈值，则各个节点的运算就可以独立进行，互不干扰。而当一旦检测到迭代次数差异过大，就会触发一些等待，避免产生过大的延迟。SSP适用于同质化比较高的集群上，即不同工作节点之间的计算性能和网络性能相差无几且比较稳定。对于一切不稳定且同质性较差的集群，还会有一些不同的平衡同步异步的做法，比如不同于当检测到相差迭代数较大时将最快的节点挂起，而是设置一个全局始终，当发现某些节点太过于陈旧时，直接将其丢弃并将其工作节点上的参数替换为参数服务器上的最新模型。除此之外，还有很多实现方式。

3.4 通信的频率

在分布式机器学习中，通信频率值两方面内容，一方面是说通信的频次间隔，称为时域频率。另一方面是指通信内容的大小，称为空间频率。相应地，优化通信频率可以从时域频率和空间频率两方面进行，即为时域滤波和空域滤波。

3.4.1 时域滤波

时域滤波旨在从通信的过程触发，通知通信的时机，减少通信的次数，进而减少通信的代价。主要有增加通信间隔、非对称的推送和获取以及计算和传输流水线。
增加通信间隔是一种简单且行之有效的分布式学习的加速方式。具体做法就是将通信频率从原来的每次本地模型更新完都要通信一次，改成本地模型多次更新后才通信一次。这种方法对于通信时间远大于计算时间的模型很有效。但是增加通信间隔会导致各个机器之间存在一定的不一致，从而对优化带来一定影响。这类方法在凸优化的情况下是有理论保证的【第七章18】。但在处理神经网络这样非凸的模型时缺乏理论保证，但是可以通过调节一些超参数获得较好地训练效果。
还可以通过非对称的推送和获取来减少通信的时间频率。在异步通信中存在两种通信操作——PUSH和PULL，前者是指从本地将更新过得参数传送到其他节点，后者是指获取最新的全局模型。对这两种操作采用不同的频率即为非对称的推送和获取。这种方法虽然和增加通信间隔一样会带来一定的精度损失，但可以通过调节一些超参数得到较好地结果。比如假设某个工作节点在训练过程中本地模型的参数变化不大，就没必要那么频繁地把很小的更新发送到参数服务器，反之亦然。
除了减少通信次数的方法之外，还有一类方法巧妙地安排了计算和通信在事件上的流水线关系，进而达到加速效果。简单地说这种流水线的方法就是，让计算的时候同时通信。可以理解通信和计算的并行，而不是非要等到模型更新结束。下图为这种方法的示意图：

在训练的时候，通信也在同步进行，当训练和通信都结束时，交换两个buffer的内容。将通信的结果进行训练，将训练的结果拿去通信。与不带流水线的方法相比，这种方法使得模型产生了延迟，但在实践中，却能有效地提高系统效率。

3.4.2 空间滤波

空间滤波的方法旨在从通信的内容触发，尽量减少通信的数据量，对传输的内容进行过滤、压缩或者量化，进而减少每一次通信的时间。
模型过滤是指对模型中参数变化小于一定阈值的参数不予通信。对于数据划分的并行模式的算法流程如下：

实践中发现，在模型训练的后期，通过这样的方法甚至可以过滤掉99%的参数，而模型任然可以收敛到原有的精度【11】。
模型低秩化处理是通过滤掉不重要的参数来减少通信量。通常情况会通过低秩分解来滤掉不重要的参数，或者说压缩参数。具体得框架如下图所示。

概括起来就是原来要传输的整个参数矩阵被分解低秩化处理后的$U$,$V$以及$\sum$矩阵。这使得实际通行的数据规模要比原始矩阵小很多。但是需要注意的是，奇异值分解本身要耗费计算资源。实践中要找到一个节省的通信开销和多耗费的计算开销之间的平衡点。
除此之外还有一种压缩参数矩阵的方法——模型量化。简单说就是将原来的32位浮点数压缩为更小的二进制数据结构。比如在1比特量化法中【12】，将原本需要通过网络传输的参数信息，从32比特的浮点数压缩为了1比特的二进制数，从而把网络通信量压缩了32倍。

虽然该方法会很大程度上降低梯度的精度，但在时间中亦然可以很好的收敛。其主要原因就是该算法每次量化均记录了量化误差，并将其与梯度一起计算在下次要量化的对象里。

4 数据与模型聚合

当信息到达接收方后是如何被聚合在一起达到多机写作学习的？这是模型聚合要解决的问题。因为分布式机器学习的方法种类多样，所以也有很多种模型聚合方式，从聚合内容来看，有些算法聚合的是模型，有些算法聚合的是数据。从聚合的执行主体来看，有些算法的执行主体是全局服务器，有些算法则是由各个工作节点自行完成的。因为现在的优化方法都是迭代进行的，所以我们要求聚合本身的时间代价要小，此外聚合算法要合理有效，整体的收敛性要基本与单机保持一致。因为模型的聚合因不同算法而异，所以阅读本节内容之前可以先阅读第六节，以便理解。

4.1 基于模型加和的聚合方法

基于模型假设的聚合方式是分布式机器学习中最为常见的一种聚合方法。该方法主要应用于数据划分的并行模式。当不同的工作节点训练各自的模型得到参数或者参数更新之后，聚合逻辑负责讲这些各自的模型聚合为一个全局模型。

4.1.1 基于全部模型加和的聚合方式

基于全部模型的算法逻辑如下表：

模型平均是一种最简单的模型聚合方式，即将各个节点的模型加和平均。BMUF在原来加和的基础上引入了冲量的概念。ADMM引入了z，使得优化得到的全局模型更加接近z。SSGD将各个节点上的梯度平均之后更新，等价于扩大了K倍的小批量更新。弹性平均SGD将工作节点的模型平均值与全局模型之间做了一个权衡，一方面保留历史状态，另一方面探索新模型。这些运算往往复杂度低，不会带来额外的压力。

4.1.2 基于部分模型加和的聚合方式

上一小结提到的聚合方式是将所有的模型通过加和聚合到一起，但是这样的做法只适用于同步并行。对于异步并行我们不可避免地只能使用基于部分模型加和的聚合方式。此外为了解决同步算法中等待所耗费的通信成本，也可以使用基于部分模型加和的聚合方式。
在ASGD算法中，聚合所有的梯度会受到最慢节点的限制。所以一个很自然的想法就是只聚合部分的节点。这也是带备份节点的同步SGD的核心思想。用$K(1+\alpha )$个工作节点来保证每次取前K个工作节点作为聚合的对象，其中$\alpha$表示备份和实际工作节点的比例。实际中$\alpha$的大小根据系统状况进行设定。
从另一个角度理解带备份节点的同步SGD算法，其实同步SGD和异步SGD的平衡状态。所以在效果上，其收敛速度快于同步SGD，慢于异步SGD，收敛精度高于异步SGD，低于同步SGD。
除了带备份节点的同步SGD算法，此外还有异步ADMM算法以及去中中心化方法等，此处不做介绍。

4.2 基于模型集成的聚合方法

基于模型参数加和或平均的聚合方法，并非所有情况下都是可取的。事实上，只有在凸优化问题中才能保证训练性能。但是，对于非凸的神经网络，由于模型输出关于模型参数非凸，模型的性能在参数平均后无法得到保证。

5 单机优化算法

单机优化算法是一个很大的范围，可以分为确定性算法和随机算法；也可以分为一阶算法和二阶算法。最优化理论中回去考虑算法的收敛性和收敛速度，此外还有一些对偶理论等优化理论。限于能力和篇幅，本文这里只对梯度下降法进行了的综述。
梯度下降算法是到目前为止最主流的优化深度学习的算法。因为通过设置合适的损失函数，我们很容易使神经网络模型变得可微。而对于可微目标函数的优化问题，梯度下降是一个很高效的方法，因为它只需要计算一阶导数，所有的参数都会有相同的计算复杂度。
但是深度学习中优化神经网络模型的问题是高度非凸非线性的。而连续空间中基于梯度的优化算法大多数只适用于凸问题。所以要得到神经网络模型的全局最优，往往要比支持向量机、logistic回归这样的机器学习问题困难很多。在实际应用中，人们常用随机梯度下降法（SGD）来优化神经网络，主要是因为深度学习实际应用中往往数据规模很大，随机算法可以通过减少每次迭代的复杂度进而减少总的复杂度，提升效率。随机梯度下降算法的一个推广就是小批量随机梯度下降。
但是日益增大的数据量以及越来越复杂的神经网络模型，随机梯度下降也显得收敛不够快。近年来，科学家们发现了一类比随机梯度下降法更为复杂并且更加适合训练神经网络的算法。这类算法在更新模型时，不只利用当前的梯度，还会利用历史上的梯度信息或是下一次迭代的信息，并且自适应地调整步长，因而也被称为Ada系列算法。包括带有冲量的随机梯度算法[14]; Nesterov加速的SGD[15]；利用历史梯度大小，针对每一维调整步长，进而适用稀疏数据的AdaGrad算法[16], 类似AdaGrad，并且结合了冲量思想的RMSProb算法[17]以及Adadelta[18]和十分流行的Adam算法[19]。这其中以Adam为代表，使用十分广泛。这类算法相较于传统的SGD，在收敛速度上有了大幅的提升，但是遗憾的是在收敛性能上都很难与SGD打成平手。于是人们迫切希望能够找到一种算法，既和Adam等算法一样快，又能收敛到SGD一样好的位置。
自从Reddi et al.[20]在2018年指出了Adam文章中的证明错误之后，自适应地算法研究领域又涌现出了很多优秀算法，如AdaShift[21]，NosAdam[22],AdaBound[23]，以及最新的Radam[24]。但是大多数算法在收敛性上和SGD还是稍逊一筹。
本文先从SGD算法开始介绍，随后介绍Adam系列算法以及Adam之后的一些Ada算法，并着重介绍Adam算法。

5.1 梯度下降法

目前主要有三种梯度下降的算法，分别为批梯度下降，随机梯度下降，小批量梯度下降三种。其区别在于使用多少数据对目标函数计算梯度。根据使用数据量的不同会造成我们参数更新得准确性和其使用的时间产生差别。

5.1.1 批梯度下降法

批梯度下降法又被称为朴素梯度下降法，是最古老的一阶算法，于1847年由Cauchy提出。梯度下降法的基本思想是：最小化目标函数在当前状态的一阶泰勒展开，从而近似地优化目标函数本身。对函数$J$，将其在当前状态${\theta }_t$处求解下述问题：$$\underset{\theta }{\min }J(\theta )=\underset{\theta }{\min }J({\theta }_t)+\nabla J({\theta }_t{)}^T(\theta -{\theta }_t)$$在机器学习中，是指使用整个训练集的数据来计算目标函数$J(\theta )$关于参数$\theta$的梯度${\nabla }_{\theta }J(\theta )$,批梯度下降的参数更新如下：$${\theta }_t={\theta }_{t-1}-\eta \times {\nabla }_{\theta }J(\theta ;x,y)$$
参数更新得伪代码如下：

for i in range(0,epochs):
	params_grad = get_gradient(loss,data,params)
	params = params-learning_rate * params_grad
1
2
3

批梯度下降法存在以下三点问题：1、参数更新速度慢；2、无法在数据大小超过内存大小时无法使用；3、没法在线上部署。但是批梯度下降的优点在于，如果目标函数是凸函数，那么可以收敛到全局最优。批梯度下降的收敛速度针对不同性质的目标函数是不同的。

5.1.2 随机梯度下降法

随机梯度下降是使用训练集中的单个元素来计算目标函数$J(\theta )$关于参数$\theta$的梯度${\nabla }_{\theta }J(\theta )$,随机梯度下降的参数更新如下：$${\theta }_t={\theta }_{t-1}-\eta {\nabla }_{\theta }J(\theta ;x^{(i)},y^{(i)})$$这里的$\eta$是学习率。
参数更新得伪代码如下：

for i in range(0,epochs):
	np.random.shuffle(data)
	for j in data:
		params_grad = get_gradient(loss,data[j],params)
		params = params-learning_rate * params_grad
1
2
3
4
5

随机梯度下降用随机采样的数据来计算梯度，是对全部数据来计算梯度的一个无偏估计，如下$${\mathbb{E}}_{i_t}\nabla J_{i_t}(\theta )={\nabla }_{\theta }J(\theta )$$批梯度下降的收敛速度针对不同性质的目标函数是不同的。随机梯度下降每次只随机抽取一个样本，随机梯度中的计算量大大减少。解决了上述批梯度下降存在的一些问题。如果目标函数是凸函数，那么可以收敛到全局最优。但是随机梯度下降法的收敛速度往往比较慢，这是因为随机梯度虽然是全体度的无偏估计，但是这种估计存在一定的方差，会引入不确定性，导致算法收敛速度下降。

5.1.3 小批量（mini-batch）随机梯度下降法

mini-batch随机梯度下降是对随机梯度下降的一个推广。不同之处在于，SGD的每一次抽样值选取一个样本，而mini-batch SGD每次迭代随机抽取n个样本。
mini-batch随机梯度下降的参数更新如下：$${\theta }_t={\theta }_{t-1}-\eta \times {\nabla }_{\theta }J(\theta ;x^{(i+n)},y^{(i+n)})$$
参数更新得伪代码如下：

for i in range(0,epochs):
	np.random.shuffle(data)
	for batch in get_batches(data,batch_size):
		params_grad = get_gradient(loss,batch,params)
		params = params-learning_rate * params_grad
1
2
3
4
5

mini-batch随机梯度下降是一种广泛应用在神经网络训练的方法。该方法有效减少了无偏估计的方差，从而提高了收敛速率。

5.2 自适应随机梯度下降法

自适应随机梯度下降法是一类算法的总称。在模型参数更新时，不只利用当前的梯度，还会用到之前的梯度信息，并且自适应地调整步长。

5.2.1 Momentum and Nesterov accelerated gradient

带冲量的方法最早于1964年由Polyak提出，被称为传统Classical Momentum（CM）是一种通过累积来梯度进而加速梯度下降的方法。其参数更新方式如下：$$v_t=\mu v_{t-1}-\eta \nabla J({\theta }_{t-1})$$$${\theta }_t={\theta }_{t-1}+v_t$$这里的$\mu$是冲量系数（mo-
mentum coeffcient）。
Nesterov加速梯度法（NAG）是Nesterov于1983年提出的。和冲量的方法一样，NAG是一个既能保证收敛性并且具有很好的收敛速度的一阶方法。对于一个光滑的凸问题，使用确定性梯度，那么NAG的收敛速率是$O(1/T^2)$(梯度下降法是$O(1/T)$)。NAG的更新方式如下：$$v_t=\mu v_{t-1}-\eta \nabla J({\theta }_{t-1}+\mu v_{t-1})$$$${\theta }_t={\theta }_{t-1}+v_t$$
这两种方法是十分比较相似的，不同之处在于带冲量的随机梯度下降法利用${\theta }_{t-1}$处的梯度进行更新，而NAG是利用${\theta }_{t-1}+\mu v_{t-1}$处的梯度进行更新。所以从实现上看，后者前者更加简单。
可以通过图1来直观理解两者之间的区别。

其中上面的是冲量加速梯度法，下面的是Nesterov加速梯度法。

5.2.2 Adagrad

The Adaptive Gradient 算法是John Duch等人于2011年提出[3]。该算法的直觉是，一般梯度比较小的维度对达到最优点也有重要的贡献，但是因为其梯度小，所以更新慢，进而容易到达一个鞍点或者局部最优。所以Adagrad对历史信息（梯度值的平方）进行了累加，并且根据历史梯度逐维度调整步长，使得梯度较小的维度获得更大的步长,其更新公式如下：$$g_t=g_{t-1}+(\nabla J({\theta }_{t-1}{)}^2)$$$${\theta }_t={\theta }_{t-1}-\frac{\eta }{(g_t+ϵ{)}^{\frac{1}{2}}}\nabla J({\theta }_{t-1})$$其中的$ϵ$是一个光滑项，防止分母为零。这个算法更适合优化具有很多局部最优点和鞍点的神经网络模型。而且这种自动调整步长的方法可以使得随机梯度下降法变得更加稳定。
该方法的缺点在于，因为更新公式中的分母项$(g_t+ϵ{)}^{\frac{1}{2}}$随着不断地训练不断变大，所以步长会越来越趋近于零，这一方面会导致最后的收敛速率很低，另一方面会使得无法收敛到足够小的极值。

5.2.3 RMSProb

RMSProb是Geoff Hinton在他的cs321课程中提出的一个自适应学习率的方法。RMSProb和AdaGrad类似，
区别在于该方法还借鉴了带冲量的随机梯度下降法的思路，对历史信息进行了指数递减平均。其更新公式如下：
$$\mathbb{E}[g_t^2]=\gamma \mathbb{E}[g_{t-1}^2]+(1-\gamma )\nabla J({\theta }_{t-1}{)}^2$$$${\theta }_t={\theta }_{t-1}-\frac{\eta }{(\mathbb{E}[g_t^2]+ϵ{)}^{\frac{1}{2}}}\nabla J({\theta }_{t-1})$$
从$g_t$的更新公式可以看出，RMSProb算法类似于对历史信息$\gamma g_{t-1}$和当下的梯度信息$\nabla J({\theta }_{t-1}{)}^2$做了一个加权平均，减少了历史信息所占的比重，加强了当前梯度的占比，避免了AdaGrad步长随着迭代次数增加逐渐趋于0的问题。而权重$\gamma$推荐设置为0.9。RMSProb方法之所以这样命名的原因是，我们观察参数迭代公式中的分母项可以发现其刚好是梯度$g$的均方根误差（root mean square error），所以我们将该方法命名为RMSProb。

5.2.4 AdaDelta

AdaDelta算法于2012年由Zeiler M D等人提出，在RMSProb的基础上进一步对累加的历史信息根据梯度的大小进行调整。在RMSProb中，每一次参数更新得大小是：
Δ θ t = − η ( E [ g t 2 ] + ϵ ) 1 2 ∇ J ( θ t − 1 ) = − η R M S [ g t 2 ] ∇ J ( θ t − 1 )

$$\begin{aligned} \Delta \theta_{t} &=-\frac{\eta}{(\mathbb{E}[g_{t}^{2}]+\epsilon)^{\frac{1}{2}}}\nabla J(\theta_{t-1})\\ &=-\frac{\eta}{RMS[g^{2}_{t}]}\nabla J(\theta_{t-1}) \end{aligned}$$ Δθt​​=−(E[gt2​]+ϵ)21​η​∇J(θt−1​)=−RMS[gt2​]η​∇J(θt−1​)​作者认为上述的更新单元的分子和分母不是很匹配，没有相同的假设。为了克服这一点，他们定义了新的指数衰减的参数更新。
$$\begin{array}{rl}\mathbb{E}[\Delta {\theta }_t^2]& =\gamma \mathbb{E}[\Delta {\theta }_{t-1}^2]+(1-\gamma )(\Delta {\theta }_t{)}^2\end{array}$$$$RMS[\Delta \theta {]}_t=(\mathbb{E}[g_t^2]+ϵ{)}^{\frac{1}{2}}$$$$\Delta {\theta }_t=-\frac{RMS[\Delta \theta {]}_{t-1}}{RMS[g_t^2]}\nabla J({\theta }_t)$$$${\theta }_{t+1}={\theta }_t+\Delta {\theta }_t$$在AdaGrad方法中，对学习率也进行了迭代更新，所以不需要设置学习率。

5.2.5 Adam

自适应动量估计法是另一种逐维度调节步长的算法。Adam同时以下两个辅助变量，并且分别按照指数衰减形式来累加梯度和梯度的平方：
$$m_t={\beta }_1{m}_{t-1}+(1-{\beta }_1)g_t$$$$v_t={\beta }_2{v}_{t-1}+(1-{\beta }_2)g_t^2$$
$m_t$和$v_t$可以看做是对梯度的均值和偏心方差的一个估计，并且作者提出可以通过以下的才做来消除估计的误差：
$$\widehat{m_t}=\frac{m_t}{1-{\beta }_1^t}$$$$\widehat{v_t}=\frac{v_t}{1-{\beta }_2^t}$$则参数值的更新就会变为如下：$${\theta }_t={\theta }_{t-1}-\frac{\eta \widehat{m_{t-1}}}{{\hat{v}}_{t-1}^{\frac{1}{2}}+ϵ}$$作者对于参数${\beta }_1$，${\beta }_2$推荐设置为0.9和0.99，$ϵ$设置为$10^{-8}$。${\beta }_1$和${\beta }_2$之所以这样设置是因为作者发现在刚开始的时间点，估计有较大偏差，所以要尽快逃出。一般在实践中，Adam是效果最好的。这是因为Adam结合了带冲量的随机梯度下降法、AdaGrad、RMSProb以及AdaDelta等算法中的所有因素：

1. 更新方向由历史梯度决定。
2. 对步长运用累加梯度的平方值进行修正。
3. 信息累加按照指数形式衰减。
   但是Radam也不是完美的，在训练的初期因为样本的缺少， Adam中的$v_t$方差会非常大。而$v_t$起到修正更新方向的作用，因此 Adam 参数的更新量的方差也会很大，进而容易落入一些局部最小值。

5.2.6 Radam

Radam是2019年由Liyuan Liu提出的，一种能够在训练初始阶段避免方差的方法。该方法直觉上可以看成一种‘预热’。所谓预热，是指训练的学习率在最初保持很小，然后逐渐增加的过程。这是因为在训练初期存在一个较大的方差，为了避免进入局部极值，或者造成‘过拟合’，需要用小一些的学习率，但是随着方差逐渐变小，就可以使得学习率增大。Radam的思路就是先找到一个$Var(v_t)$的函数，随后计算其线性插值权重$r_t$，然后根据$r_t$对学习率进行修正。作者定义了${\rho }_{\infty }=\frac{2}{1-{\beta }_2^0}-1$,参数更新方式如下：
$$m_t={\beta }_1{m}_{t-1}+(1-{\beta }_1)g_t$$$$v_t={\beta }_2{v}_{t-1}+(1-{\beta }_2)g_t^2$$$$\widehat{m_t}=\frac{m_t}{1-{\beta }_1^t}$$$${\rho }_t={\rho }_{\infty }-\frac{2t{\beta }_2^t}{1-{\beta }_2^t}$$
当方差是可控的时，即${\rho }_t>4$:
$$r_t=(\frac{({\rho }_t-4)({\rho }_t-2){\rho }_{\infty }}{({\rho }_{\infty }-4)({\rho }_{\infty }-4){\rho }_t}{)}^{\frac{1}{2}}$$$${\theta }_t={\theta }_{t-1}-\eta r_t\widehat{m_t}(\frac{1-{\beta }_2^t}{v_t}{)}^{\frac{1}{2}}$$
否则直接按照带冲量随机梯度下降法：
$${\theta }_t={\theta }_{t-1}-\eta \widehat{m_t}$$
该方法在一些应用场景下收敛性可以优于Adam，并且该方法具有很好的稳定性。

6 分布式优化算法

分布式机器学习算法多种多样，首先会介绍多种同步算法，然后介绍异步算法，随后介绍如何对两种算法有效融合，最后介绍两种模型并行算法。下面对常见的算法汇总如下表：

6.1 同步算法

同步算法与之对应的是通信中的同步通信。在同步算法中，不可避免地存在一个等待现象，就是等待所有的工作节点均运行到一个同步屏障之后，再进行聚合、分发。反复迭代下去。本小节会对几种比较常见的同步算法进行介绍。

6.1.1 同步SGD

将随机梯度下降法套用到同步的BSP框架中，所产生的的最基本的算法就是同步SGD（SSGD）【26】。SSGD对应的算法流程如下：

可以看到当每次选取的样本数为b时,同步的SGD是一个小批量为bK的SGD。但是SGD的收敛速度较慢，这意味着要进行多次迭代。因而不可避免地会造成很多通信，这是该算法的弊端。可以通过前面提到的通信机制降低通信时间占比。此外，对于在上一章提到了多种比较新的自适应地梯度下降法，比如Adam，Radam这些收敛速度较快的方法，也可以带入到上述的同步算法中。

6.1.2 模型平均方法（MA）

前面提到的SSGD由于通信比较频繁而造成的通信与时间的占比较大的问题，使用模型平均方法【27】可以很好地解决。MA算法的思想有点类似前面讲到的通信机制中时域滤波有点类似。具体思想是对本地的模型进行多轮的更新迭代，知道模型收敛或者迭代次数达到某个阈值，在进行一次全局的模型平均，并以此均值作为最新的全局模型继续训练。流程如下。

MA的方法极端一些，可以等到当各个工作节点上的子模型收敛了，再进行一次平均。这样的做法对于凸的问题是可以保证收敛的，但是对于非凸的情况，是难以保证收敛的。因为子模型因为数据不足很容易落入局部极值点。这种情况下对参数的平均无法保证收敛。所以对于非凸的问题，比如神经网络，一般的做法是进行一定的迭代数之后就做一次全局权重的更新，这样就降低了其子模型落入局部极值的可能，进而更好地保证全局收敛。

6.1.3 BMUF算法

BMUF（Block-wise Model Update Filtering）块模型更新过滤【28】是Chen K 等人于2016年提出的分布式机器学习算法。该算法是基于数据块的冲量思想对MA进行了改进。BMUF的算法流程如下：

BMUF的核心思想是利用了全局的冲量，从而加快模型的收敛速度。

6.1.4 ADMM算法

在MA中，来自各个工作节点的模型被简单的平均。ADMM算法通过求解一个全局一致的优化问题进行了模型的聚合。使用K台机器进行数据划分并行的分布式机器学可以表示为求解下面的优化问题：$$\underset{{\omega }^0,\dots ,{\omega }^k,\dots ,{\omega }^K}{\min }\sum _{k=1}^K{\hat{l}}^k({\omega }^k)$$ADMM算法引入了一个辅助变量z来控制各个工作节点上的模型${\omega }^k$的差异。可转化为求解下面带约束优化问题：$$\underset{{\omega }^0,\dots ,{\omega }^k,\dots ,{\omega }^K}{\min }\sum _{k=1}^K{\hat{l}}^k({\omega }^k)s.t{\omega }^k-z=0$$
对上述问题使用增广拉格朗日乘子法即可转化为$$\underset{{\omega }^0,\dots ,{\omega }^k,\dots ,{\omega }^K}{\min }\sum _{k=1}^K({\hat{l}}^k({\omega }^k)+({\lambda }_t^k{)}^T({\omega }^k-z_t)+\frac{\rho }{2}||{\omega }^k-z_t|{|}_2^2)$$下面是ADMM算法在分布式机器学习中的算法流程。
${\lambda }_{t+1}^k={\lambda }_t^k+\rho ({\omega }_t^k-z_t)$
$${\omega }_{t+1}^k=\underset{\omega }{\mathrm{argmin}}({\hat{l}}^k({\omega }^k)+({\lambda }_t^k{)}^T({\omega }^k-z_t)+\frac{\rho }{2}||{\omega }^k-z_t|{|}_2^2)$$$z_{t+1}=\frac{1}{K}(\sum _{k=1}^K{\omega }_t^k+\frac{1}{\rho }{\lambda }_t^k)$

// 工作节点K
Initialize：本地参数$omega_{0}^{k},\lambda_{t}^{k}$,工作节点数K，全局迭代数T$
for t=0,1,2,3,...,T-1 do
	获取全局对偶变量$z_{t}$
	对本地对偶变量$\lambda_{t}^{k}$更新：$\lambda_{t+1}^{k}=\lambda_{t}^{k}+\rho(\omega_{t}^{k}-z_{t})$
	求解局部最优问题，更新本地参数：$$\omega_{t+1}^{k} = \argmin \limits_{\omega}(\hat{l}^{k}   (\omega^{k})+(\lambda_{t}^{k})^{T}(\omega^{k}-z_{t})+\frac{\rho}{2}||\omega^{k}-z_{t}||_{2}^{2})
	$$
	
	将$\omega_{t+1}^{k},\lambda_{t+1}^{k}$发往主节点。
end for

//主节点
Initialize：本地参数$z_{0}$,局部工作节点数K
Repeat：
	Repeat：
		等待收取工作节点中传来的$\omega_{t}^{k},\lambda_{t}^{k}$
	Unitil：
		收到K个节点的局部模型
		进行对全局的对偶变量的修改$z_{t+1}=\frac{1}{K}(\sum \limits_{k=1}^{K}\omega_{t}^{k}+\frac{1}{\rho}\lambda_{t}^{k})$
		将$z_{t+1}$发回各个工作节点。
Unitil 终止
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

可以看出ADMM算法加入的全局正则项$z_t$使得模型不容易出现过拟合，在测试集上往往会有比较好的表现。但是缺点在于，要多消耗一些算力。

6.1.5 弹性平均SGD算法

前面介绍的几种算法，都会在某个时刻聚合出来一个全局模型，并用其来代替本地模型。但这对于非凸的问题来说，各个工作节点可能是在不同的搜索空间里寻找最优点。由于搜索方向不同，得到的模型也不尽相同，所以简单的中心话聚合会抹杀各个工作节点自身探索的信息。为此科研人员提出了一种非完全一致的分布式机器学习算法，称为弹性平均SGD【29】。该方法的出发点与ADMM相似，但是不强求各个工作节点继承全局模型z。定义${\omega }^k$为第k个节点上的模型，$\bar{\omega }$为全局模型，则可以将分布式优化描述为：$$\underset{{\omega }^0,\dots ,{\omega }^k,\dots ,{\omega }^K}{\min }\sum _{k=1}^K{\hat{l}}^k({\omega }^k)+\frac{\rho }{2}||{\omega }^k-\bar{\omega }|{|}^2$$可以看出该算法是要优化工作节点本身的损失函数，也要使得工作节点上的模型与全局模型尽量相似。其算法流程如下：

// 工作节点K
Initialize：全局参数$omega_{t}$,本地参数$omega_{t}$,，工作节点数K，全局迭代数T,学习率$/eta_{m}$，约束系数$\alpha$
for t=0,1,2,3,...,T-1 do
	从训练集S中随机抽取或者在线获取样本（或小批量）$i_{t}^{k} \in [n]$
	计算这个样本上的随机梯度$\nabla f_{i_{t}^{k}}(\omega_{t})$
	更新本地模型，更新时要考虑当前模型与全局模型的差异：
		$\omega_{t}^{k} =\omega_{t}^{k}-\eta_{m} \nabla f_{i_{t}^{k}}(\omega_{t}^{k})-\alpha(\omega_{t}^{k}-\omega_{t})$
	同步通信得到所有工作节点上的局部参数之和$\sum \limits_{k=1}^{K}\omega_{t}^{k}$
	更新全局参数
	end for
	同步通信获得所有节点上的参数的平均$\bar{\omega_{t+1}}=\frac{1}{K}\sum \limits_{k=1}^{K}\omega_{t}^{k}$
	计算带冲量的更新$\Delta_{t}=\mu_{t}\Delta_{t-1}+\zeta_{t}(\bar{\omega_{t+1}}-\omega_{t})$
	更新全局参数$\omega_{t+1}=(1-\beta)\omega_{t}+\beta(\frac{1}{K}\sum \limits_{k=1}^{K}\omega_{t}^{k})$
end for 
1
2
3
4
5
6
7
8
9
10
11
12
13
14

可以看出EASGD在本地模型和服务器模型更新时都同时兼顾了全局异质性和本地模型的独立性。

6.2 异步算法

异步算法是指在异步的通信步调下，各个节点不再相互等待，而是以一个或多个全局服务器作为中介，实现对全局模型的更新读取。这样做的好处是减少等待时间，缺点是可能会有较高的延迟。本节将会对常见的异步算法进行介绍分析对比。

6.2.1 异步SGD

异步SGD【30】与同步SGD类似，是比较基础的异步算法。其主要思路是，当参数服务器接收到来自工作节点的参数梯度之后直接加到全局模型上。其算法流程如下：

// 工作节点K
Initialize：全局参数$\omega$,工作节点的局部模型，工作节点数K，当前节点的编号k，全局迭代数T，学习率$\eta$
for t=0,1,2,3,...,T-1 do
	从参数服务器获取当前模型$\omega_{t}^{k}$
	从训练集S中随机抽取或者在线获取样本（或小批量）$i_{t}^{k} \in [n]$
	计算这个样本上的随机梯度$g_{t}^{k}=\nabla f_{i_{t}^{k}}(\omega_{t})$
	将$g_{t}^{k}$发往参数服务器
end for

//参数服务器
Repeat：
	Repeat：
		等待
	Unitil 收到新信息：
		if 收到更新梯度信息 do：
			更新服务器端的模型$\omega = \omega-\eta g_{t}^{k}$
		end if
		if 收到请求参数信息 do：
			发送最新的参数到对应的工作节点
		end if
Unitil 终止
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

异步SGD虽然避免了同步等待的开销，但是又引入了一些延迟。如何理解延迟呢？当工作节点计算梯度的时候是针对当前的全局模型进行的，但是当这个梯度发送到参数服务器之后，服务器端的模型已经被修改了，因此会出现梯度和模型失配的问题。比如说用一个很久的梯度去更新一个已经被别的工作节点优化了好几轮的新模型。假设延迟为$\tau$,则ASGD的更新规则如下：$${\omega }_{t+\tau +1}={\omega }_{t+\tau }-\eta g_t$$对比单机版的更新规则：$${\omega }_{t+\tau +1}={\omega }_{t+\tau }-\eta g_{t+\tau }$$可以发现ASGD和SGD的更新梯度上存在一个$\tau$的“延迟”。这可能导致模型在优化时出现抖动现象，甚至是无法收敛。

6.2.2 Hogwild!算法

异步并行算法当要在共享内存的系统上运行时，会考虑对内存枷锁，以保证写入的一致性。Hogwild!算法【31】算法为了提高训练过程数据的吞吐量，选择了无锁的全局模式访问，其算法流程如下：

可能我们很难想象当在写入参数更新时不先对写的操作加锁，那如果写入的信息被覆盖了肯定会对训练过程造成不好的影响。但是当我们对模型访问的稀疏性限制了之后，也就是利用通信时域滤波对通信内容限制之间，这种访问冲突就会很少。这也是该算法收敛性的依据。

6.2.3 AdaDelay算法【32】

在对梯度下降法及其衍生的算法介绍时，提到了自适应步长的概念。我们也可以应用自适应步长这个概念来解决更新延迟的问题。直观地讲，对于那些延迟较高的梯度，其可靠性降低，因而可以减少其步长。
假设t时刻的模型延迟是${\tau }_t$，那么学习率$\alpha (t,{\tau }_t)$的计算如下：$$\eta (t,{\tau }_t)=c\sqrt{t+{\tau }_t}$$$$\alpha (t,{\tau }_t)=(L+\eta (t,{\tau }_t){)}^{-1}$$这里的L是指Lipschitz常数，用以确保学习步长不会超过$\frac{1}{L}$, c用来调节延迟方差和梯度均值对步长的影响。可以直观地看到，当延迟增大以及迭代数增加时,步长会x相应减小。当c=0时，就是常见的固定步长的方法。在实际中，AdaDelay采用动态的c，并且对每个参数维度分别计算步长位移。$${\eta }_j(t,{\tau }_t)=c_j\sqrt{t+{\tau }_t}$$$$c_j=\sqrt{\frac{1}{t}\sum _{s=1}^t\frac{i}{s+{\tau }_s}{g}_j^2(s-{\tau }_s)}$$
该方法是一种行之有效的方法，在一定假设条件下，该算法可以保证收敛。

6.2.4 带有延迟补偿的ASGD算法（DC-ASGD）

AdaDelay的思路是对那些延迟较大的模型梯度，减少其学习步长。还有另外一种做法就是带有延迟的梯度进行补偿。DC-ASGD【33】的核心思想就是这样，其用对$g({\omega }_{t+\tau })$在${\omega }_t$处进行泰勒展开：$$g({\omega }_{t+\tau })=g({\omega }_t)+(\nabla g({\omega }_t){)}^T({\omega }_{t+\tau }-{\omega }_t)+O({\omega }_{t+\tau }-{\omega }_t^2)I$$忽略掉高阶项，我们可以用$g({\omega }_t)$对$g({\omega }_{t+\tau })$进行估计。上述问题的难点主要在于$\nabla g({\omega }_t)$的计算，也就是损失函数在${\omega }_t$的Hession矩阵。对于一个深度学习模型而言，Hession阵的计算需要花费巨大的计算量和存储空间，这也是为什么我们在优化深度学习任务时，不用二阶方法。DC-ASGD的方法使用了一种对Hesiion矩阵的近似。首先记$g({\omega }_t)$的外积为$G({\omega }_t)$，根据一系列的数学推导得出$G({\omega }_t)$是${\omega }_t$的Hession矩阵的无偏估计。引入超参数$\lambda$,用$\lambda G({\omega }_t)$能在无偏估计的基础上缩减方差。因而DC-ASGD的算法流程如下：

// 工作节点K
Initialize：全局参数$\omega$,工作节点的局部模型，工作节点数K，当前节点的编号k，全局迭代数T，学习率$\eta_{t}$
for t=0,1,2,3,...,T-1 do
	从参数服务器获取当前模型$\omega_{t}^{k}$
	从训练集S中随机抽取或者在线获取样本（或小批量）$i_{t}^{k} \in [n]$
	计算这个样本上的随机梯度$g_{t}^{k}=\nabla f_{i_{t}^{k}}(\omega_{t})$
	将$g_{t}^{k}$发往参数服务器
end for

//参数服务器
Initialize:参数服务器中存储的全局参数$\omega$，每个工作节点最近取走的参数备份$\omega^{bak_{k}},k=1,2,3,\dots,K$
Repeat：
	Repeat：
		等待
	Unitil 收到新信息：
		if 收到更新梯度信息 do：
			更新服务器端的模型$\omega = \omega-\eta_{t} (g_{t}^{k}+\lambda_{t}g_{t}^{k}\odot g_{t}^{k}\odot(\omega^{{k}}-\omega^{bak_{k}}))$
		end if
		if 收到请求参数信息 do：
			发送最新的参数到对应的工作节点
			更新k在服务器上的备份模型$\omega^{bak_{k}}=\omega$
		end if
Unitil 终止
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

DC-ASGD算法在CIAFR-10上以及IMAGENET上的测试结果显示，其加速比高于SSGD，并且收敛效果优于ASGD，综合下来是一个优秀的算法。

6.3 同步和异步的对比融合

6.3.1 对比

一般来看，SSGD的进度要不ASGD高，与单机的SGD算法更加接近。DC-ASGD算法由于采用了延迟补偿，精度有所提高。基于模型平均的算法MA和BMUF比其他算法精度要差一些，其中后者因为引入了冲量，收敛更快一些。每种算法在不同的应用场景之下各有优势。在通信代价不构成瓶颈的前提下，SSGD是一种很好的选择。当通信成为短板时，可以使用异步算法。当异步算法的延迟很高时，可以使用DC-ASGD来缓解延迟问题。如果使用异步方法，但通信开销还是大于计算开销时，可以使用基于模型平均的方法。总之，没有最好的，只有最合适的。

6.3.2 融合

同步和异步各有优缺点，如果能够把两者结合起来，取长补短，或许可以达到很好的效果。在上面对不同方法的对比中，我们发现不同算法有不同的应用场景。然而在实际中，我们的场景或许不是单一的，这种场景复杂的情况下，需要对场景进行分解，然后每个比较一致的场景下选用特定的算法。比如，对于机器数目很多、本地工作节点负载不均衡的集群。可以先根据每个节点的运算能力和通信能力进行聚类，将性能相近的节点分为不同的组。由于组内的各组运算速度差异较小，可以采用同步并行。组件的运算速度差异介意采用异步并行的方式。这种混合的方式既不会让运行速度慢的本地工作节点过度拖累全局训练速度，也不会引入过大的异步延迟进而影响收敛精度。下图展示了一个能够融合同步异步的原型系统架构。

6.4 模型并行算法

前面介绍的都是基于数据划分的并行算法，这一小节讲解基于模型划分的并行算法。介绍两种比较经典的算法：DistBelif和AlexNet。

6.4.1 DistBelif

DistBelif的整个架构如下图所示，由于其大数据、大模型的特点，即采用了数据划分，又采用了模型划分。当模型较大时，加速比随着机器数目的增加而提高，最好的情况是128台机器实现12倍加速比。

6.4.2 AlexNet

AlexNet是用于模型图像分类的一个著名算法。AlexNet需要在两个GPU显卡上并行完成。在AlexNet中，卷积核被划分为两组，在两块GPU上并行训练。不过，AlexNet的不同之处在于，第一个卷积层到第二个卷积层、第三个卷积层到第四个卷积层以及第四个到第五个之间没有依赖，因而没有通信。这样做会减少通信的数据量，提高并行效率。AlexNet在提高效率方面进行了有益的尝试，通过放弃一些交互，换来整体效率的提升。

6 总结讨论

在分布式机器学习这个领域还有很多研究问题有待探索，有工程方面的也有数学方面的等等。希望未来能有更多的人加入到该领域的研究，发展和完善分布式机器学习的技术和理论。

参考文献

[1] Deng J, Dong W, Socher R, et al. Imagenet: A large-scale hierarchical image database[C]//2009 IEEE conference on computer vision and pattern recognition. Ieee, 2009: 248-255.
[2] Amodei D, Ananthanarayanan S, Anubhai R, et al. Deep speech 2: End-to-end speech recognition in english and mandarin[C]//International conference on machine learning. 2016: 173-182.
[3] Bahdanau D, Cho K, Bengio Y. Neural machine translation by jointly learning to align and translate[J]. arXiv preprint arXiv:1409.0473, 2014.
[4] Silver D, Huang A, Maddison C J, et al. Mastering the game of Go with deep neural networks and tree search[J]. nature, 2016, 529(7587): 484-489.
[5] Yuan J, Gao F, Ho Q, et al. Lightlda: Big topic models on modest computer clusters[C]//Proceedings of the 24th International Conference on World Wide Web. 2015: 1351-1361.
[6] Arivazhagan N, Bapna A, Firat O, et al. Massively multilingual neural machine translation in the wild: Findings and challenges[J]. arXiv preprint arXiv:1907.05019, 2019.
[7] Richtárik P, Takáč M. Distributed coordinate descent method for learning with big data[J]. The Journal of Machine Learning Research, 2016, 17(1): 2657-2681.
[8] Sun S, Chen W, Bian J, et al. Slim-DP: a multi-agent system for communication-efficient distributed deep learning[C]//Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems. 2018: 721-729.
[9] Ho Q, Cipar J, Cui H, et al. More effective distributed ml via a stale synchronous parallel parameter server[C]//Advances in neural information processing systems. 2013: 1223-1231.
[10] Shamir O. Open problem: Is averaging needed for strongly convex stochastic gradient descent?[C]//Conference on Learning Theory. 2012: 47.1-47.3.
[11] Lin Y, Han S, Mao H, et al. Deep gradient compression: Reducing the communication bandwidth for distributed training[J]. arXiv preprint arXiv:1712.01887, 2017.
[12] Seide F, Fu H, Droppo J, et al. 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech dnns[C]//Fifteenth Annual Conference of the International Speech Communication Association. 2014.
[13] Sun S, Chen W, Bian J, et al. Ensemble-compression: A new method for parallel training of deep neural networks[C]//Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, Cham, 2017: 187-202.
[14] Sutskever I, Martens J, Dahl G, et al. On the importance of initialization and mo-mentum in deep learning. International conference on machine learning. 2013.
[15] Yurii Nesterov. method for unconstrained convex minimization problem with the rate of convergence o(1/k2). Doklady ANSSSR (translated as Soviet.Math.Docl.), 269:543–547, 1983.
[16] Duchi J, Hazan E, Singer Y. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 2011.
[17] Tieleman T, Hinge G. Leecture6.5-rmsprob: Divide the gradient by a running average of its recent magnitude… COURSERA: Neural Networks for Machine Learning, 2012
[18] Zeiler M D. Adadelta: an adaptive learning rate method. arXiv preprint. arXiv: 1212.5701, 2012.
[19] Kingma D P, Ba J. Adam: A method for stochastic optimization[J]… arXiv preprint arXiv:1412.6980, 2014.
[20] Reddi, S. J., Kale, S., and Kumar., S. On the convergence of adam and beyond. Pro-ceedings of the 6th International Conference on Learning Representations (ICLR), 2018.
[21] Zhou, Z., Zhang, Q., Lu, G., Wang, H., Zhang, W., and Yu, Y. Adashift: Decorre-lation and convergence of adaptive learning rate methods… Proceedings of 7th Inter-national Conference on Learning Representations (ICLR), 2019.
[22] Huang, H., Wang, C., and Dong., B. Nostalgic adam: Weighting more of the past gra-dients when designing the adaptive learning rate. . arXiv preprint arXiv: 1805.07557, 2019.
[23] Luo, L., Xiong, Y., Liu, Y., and Sun, X. Adaptive gradi- ent methods with dynamic bound of learning rate. Proceedings of 7th International Conference on Learning Representations, 2019.
[24] Liu L., Jiang, H., He, P., Chen, W., Liu, X., Gao, J., Han, J. On the Variance of the Adaptive Learning Rate and Beyond. Proceedings of 8th International Conference on Learning Representations, 2020.
[25] Polyak, B.T. Some methods of speeding up the convergence of iteration methods… USSR Computational Mathematics and Mathematical Physics, 1964.
[26] Zinkevich M, Weimer M, Li L, et al. Parallelized stochastic gradient descent[C]//Advances in neural information processing systems. 2010: 2595-2603.
[27] McDonald R, Hall K, Mann G. Distributed training strategies for the structured perceptron[C]//Human language technologies: The 2010 annual conference of the North American chapter of the association for computational linguistics. 2010: 456-464.
[28] Chen K, Huo Q. Scalable training of deep learning machines by incremental block training with intra-block parallel optimization and blockwise model-update filtering[C]//2016 ieee international conference on acoustics, speech and signal processing (icassp). IEEE, 2016: 5880-5884.
[29] Zhang S, Choromanska A E, LeCun Y. Deep learning with elastic averaging SGD[C]//Advances in neural information processing systems. 2015: 685-693.
[30] Agarwal A, Duchi J C. Distributed delayed stochastic optimization[C]//Advances in Neural Information Processing Systems. 2011: 873-881.
[31] Recht B, Re C, Wright S, et al. Hogwild: A lock-free approach to parallelizing stochastic gradient descent[C]//Advances in neural information processing systems. 2011: 693-701.
[32] Sra S, Yu A W, Li M, et al. Adadelay: Delay adaptive distributed stochastic convex optimization[J]. arXiv preprint arXiv:1508.05003, 2015.
[33] Zheng S, Meng Q, Wang T, et al. Asynchronous stochastic gradient descent with delay compensation[C]//International Conference on Machine Learning. 2017: 4120-4129.