\\介绍\\随机梯度下降（SGD）由于其极高的效率，成为目前大多数机器学习应用中最常见的训练方法。在考虑计算效率时，mini-batchSGD同时计算多个随机梯度，似乎不符合计算效率的要求。但是mini-batchSGD可以在不同网络之间并行化，所以它是现代分布式深度学习应用的更好选择。有以下两个原因：（1）mini-batchSGD可以利用在GPU上的局部计算并行性；（2）降低参数更新频率有助于减轻不同设备间的通信瓶颈，这对于大型模型的分布式设置是十分重要的。\\目前有些方法为了减少训练时间，使用大批量的SGD。但是这一选择是错误的，因为它没有正确考虑设备的局部并行化以及设备间的通信效率。尤其是当设备的数量增加时，每台设备的并行化程度会严重约束通信效率。\\为了解决这个问题，我们提出在每个网络上使用局部SGD的一种新变体。局部SGD在几次迭代后（无通信）对网络的平均来更新参数。我们发现，调整通信间隔中的迭代次数可以成功地将局部并行性与通信延迟分离。\\我们进一步将该想法推广到去中心化和异质的系统上。如下图所示的层次化网络结构推动了局部SGD的层次化扩展。\\\\图1数据中心某集群的层次化网络结构示意图。\\除此之外，端用户的设备，例如移动手机，组成了巨大的异质网络。在这里，机器学习模型的分布式计算和数据局部训练具有极大的优势。\\论文贡献\\我们提出了一个新的局部SGD的层次化扩展训练框架，进一步提高了局部SGD对实际应用中异质分布系统的适应性。对于实际情况下多服务器或数据中心的训练，层次结构的局部SGD比局部SGD和mini-batchSGD均提供了更好的表现性能，尤其是在达到同样准确率的情况下，层次结构的SGD提高了通信效率。\\我们在多个计算机视觉模型上进行了局部SGD训练方法的实证研究，实验显示了该方法相比于mini-batchSGD有明显优势。结果显示局部SGD在保证预测准确率的前提下大大降低了通信需求。在ImageNet上，局部SGD的表现超出了现有的大批量训练方法约1.5倍。\\分布式训练\\我们主要考虑标准的求和结构的优化问题：\\\\其中w是模型（神经网络）的参数，fi是第i个训练样本的损失函数。\\Mini-batchSGD表达式为：\\\\在分布式设置中，数据样本被划分到K个设备上，每个设备只能访问局部的训练数据。在这种情况下的mini-batchSGD算法表达式为：\\\\这里第k个设备的mini-batch来自本地数据，这K个设备并行计算梯度，然后通过平均来同步局部梯度。\\局部SGD\\与mini-batchSGD相比，局部SGD先在每个设备上进行局部的序列更新，然后累积K个设备之间的参数更新，如下图所示。\\\\图2一轮局部SGD（左）与一次mini-batchSGD（右）对比。每个设置中批尺寸B_loc均为2，对于局部SGD，进行H=3次局部迭代。局部参数更新由红色箭头表示，而全局平均（同步）由紫色箭头表示。\\每个网络k反复地从局部数据中提取固定数量的样本，批尺寸为B_loc，然后进行H次局部参数更新，在此之后再与其他设备进行全局参数累积。因此，每一次同步（通信），局部SGD在每一台设备上已经访问了B_glob=HxB_loc个训练样本（亦为梯度计算次数）。\\一轮局部SGD可以描述为：\\\\其中表示设备k上的局部模型在t次全局同步以及h次局部更新之后的参数。在H次局部更新后，同步的全局模型通过平均K个模型得到：\\\\层次化局部SGD\\实际的系统都会有不同的通信带宽，因此我们提出将局部SGD部署在不同层级上，使之适应相应层级的计算能力与通信效率的平衡。层次化局部SGD在系统适应性和表现性能上均具有显著优势。\\下图是层次化局部SGD的示意图：\\\\图3层次化局部SGD示意图。设批尺寸B_loc=2，局部迭代次数为H=3，区块迭代次数H_b=2。局部参数更新用红色箭头表示，而区块和全局同步分别用紫色和黑色箭头表示。\\我们以GPU计算集群为例，将大量GPU成组分布于几个机器上，将每组称为一个GPU区块。层次化的局部SGD连续更新每块GPU上的局部模型，在H次局部更新之后，会在GPU区块内部进行一次快速同步。在外层，在H_b次区块更新后，会对所有的GPU区块进行全局的同步。完整的过程可以表达如下：\\\\实验结果\\在这一部分，我们通过实验分析对比mini-batchSGD和我们提出的层次化局部SGD的性能。\\数据集\\CIFAR-10/100。训练集包含50K张彩色图像，测试集包含10K张彩色图像，大小均为32x32，分别具有10个和100个类别标签。我们采用标准数据增强方法和预处理方法处理数据集。\\tImageNet。ILSVRC2012图像分类数据集包含128百万张训练图像，50K张验证图像，具有1000个类别标签。网络输入图像大小为224x224。\模型选择\\我们用ResNet-20来测试（层次化）局部SGD在CIFAR-10/100上的表现，然后用ResNet-50来测试（层次化）局部SGD在ImageNet上的准确率和可扩展性。我们也用DenseNet和WideResNet进行了实验，验证局部SGD对不同模型的泛化能力。\\CIFAR-10/100实验\\局部SGD训练\对于CIFAR-10，我们在2个服务器上进行局部SGD训练，每个服务器有1块GPU。\\保证准确率的同时提高通信效率\\\\图4通过局部SGD在CIFAR-10数据集上训练ResNet-20。批尺寸B_loc=128，局部更新次数从1到32。\\从图4中可以看出，局部SGD在保证了准确率的同时，极大提高了通信效率，并且具有更快的收敛速度。在实验中，mini-batchSGD是局部SGD的一种特殊形式，（局部迭代次数）H=1。从图4(a)可以看出，对于同样数量的样本，局部SGD缓解了通信瓶颈的问题。图4(b)给出了局部SGD对于整体训练时间的影响：局部迭代次数H越大，影响越大，H=32时局部SGD至少比mini-batchSGD快3倍。从图4(c)中可以看出，对于不同的H值，最终的准确率会趋于稳定，并且与测试准确率并无大的差异。\\比“大批量训练”更好的泛化能力\\\\表1通过局部SGD在CIFAR-10数据集上训练ResNet-20。给出了固定访问数据量B_glob时，mini-batchSGD和局部SGD的top-1测试准确率。\\从表1中可以看出当访问同样的样本数时，局部SGD比mini-batchSGD具有更好的泛化能力。大批量训练方法提出了很多技巧来克服收敛问题，包括改变学习率和逐渐开始。Mini-batchSGD如果采用大批量训练方法仍然会有很多问题，而局部SGD通过局部迭代次数很自然的解决了这个问题。\\层次化的局部SGD训练\下面我们在分布式异质系统上测试我们提出的训练方法。我们模仿真实情况的设定，即计算设备（GPU）在不同的服务器上的集群，网络带宽限制了大型模型更新所需的通信效率。\\\\表2随机SGD在CIFAR-10数据集上训练ResNet-20模型（5x2GPU集群）。在局部批尺寸B_loc和区块迭代次数H_b固定的情况下，我们给出了H从1到1024，训练时间的变化情况。\\训练时间vs局部迭代步数\\表2给出了局部SGD与训练时间的关系。通信需求主要来自于5个节点的全局同步，每个节点有2个GPU。我们发现过大的局部更新迭代次数甚至会降低局部更新带来的通信优势。这一性能降级或许是由于独立的局部过程增加了同步时间。\\层次化局部SGD对网络延迟的高容忍度\\\\图5层次化局部SGD在CIFAR-10数据集上训练ResNet-20模型（2x2GPU集群）表现性能。局部迭代次数H=2（a）训练准确率vs时间（b）每次全局同步有1秒延迟情况下的训练准确率vs时间（c）每次全局同步有50秒延迟情况下的训练准确率vs时间.\\层次化的局部SGD对网络延迟具有鲁棒性。例如，对于固定的H=2，通过减少在所有模型上进行全局同步的次数，我们可以减少一定的训练时间，如图5(a)所示。图5(b)进一步展示了网络对于较慢的通信的影响，其中每个全局通信都增加了1秒的延时。图5(c)显示增加区块内迭代次数能够克服通信瓶颈的问题，而不会对表现造成影响。\\层次化局部SGD能够进行更大的扩展并且具有更好的表现\\\\表3层次化局部SGD在CIFAR-10数据集上训练ResNet-20模型（10GPUKubernetes集群）表现性能。\\表3对比了mini-batchSGD和层次化的局部SGD。我们可以发现，具有足够区块迭代次数的层次化局部SGD可以有效缓解准确率降低的问题。并且，内节点同步次数更多的层次化局部SGD的表现也超过了局部SGD。结合表2和表3可以发现，层次化的局部SGD的表现超过了局部SGD和mini-batchSGD的训练速度和模型表现。\\ImageNet-1K实验\\\\图6局部SGD在ImageNet-1k数据集上训练ResNet-50模型（15x2GPU集群）表现性能。\\图6显示我们可以通过局部SGD在15x2GPU集群上有效训练（快1.5倍）ResNet-50。在达到同样准确率时，局部SGD只需要很少的时间和同步次数，节省了计算量，并且提高了通信效率。\\结论\\在这篇文章中，我们利用局部SGD的思想，将其扩展至去中心化和异质的系统环境。我们提出了层次化的局部SGD，能够有效适应于实际情况中的异质系统。此外，我们实证研究了局部SGD在不同的计算机视觉模型上的表现，实验显示算法在整体性能和通信效率方面均有显著提高。\\查看论文原文：Don'tUseLargeMini-Batches,UseLocalSGD\\感谢蔡芳芳对本文的审校。

1引言

机器学习是指通过计算机学习数据中的内在规律性信息，获得新的经验和知识，以提高计算机的智能性，使计算机能够像人那样去决策[1]。通常我们在学习一个模型时首先要收集大量关于这个问题的数据，其目标属性作为样本标签是已知的，记为y.其次根据实际问题建立预测模型，预测模型对样本标签的预测为h(x)，显然y与h(x)之间的误差越小越好，这个误差被称为损失函数。因此，机器学习中的许多问题都可以归结为：计算损失函数和的近似最小值问题。

                                        （1）

其中表示训练集的数据，表示训练集所含样本点的个数，表示第个样本点的损失函数，表示所有样本点的平均损失函数[2]。我们要解决的问题是寻找模型中的最优参数使得尽可能的小，梯度下降算法常用于解决此问题。特别的，本文中所讨论的梯度下降算法基于3个前提：针对有限训练集；为光滑函数；是强凸的。

2梯度下降算法

常见的训练学习算法有全梯度下降算法(Fullgradientdescent），随机梯度下降算法（Stochasticgradient descent），随机平均梯度下降算法（Stochasticaveragegradientdescent）和小批量梯度下降算法（Mini-batchgradientdescent）,它们都是为了正确地调节权重向量，通过为每个权重计算一个梯度，从而更新权值，使目标函数尽可能最小化。其差别在于样本的使用方式不同。

2.1全梯度下降算法（FG）

计算训练集所有样本误差，对其求和再取平均值作为目标函数。权重向量沿其梯度相反的方向移动，从而使当前目标函数减少得最多。将全体训练样本的目标函数看做是一种在权重高维空间的丘陵景观，最小化所有样本的目标函数即为寻找丘陵最低洼的地方。负梯度方向表示丘陵这一点的最速下降方向，沿这一方向接近最小值，那里的输出平均损失函数值最低[3]。其迭代形式为

                                                （2）

若用来实现的最小值，则此方法在固定步长下可实现线性收敛速度[4][5]

                                 

这里，且取决于的数值情况。除快速的收敛速度，全梯度算法并不具吸引力，因为当n很大时，迭代成本与n线性相关[6]。

2.2随机梯度下降算法（SG）

由于FG每迭代更新一次权重都需要计算所有样本误差，而实际问题中经常有上亿的训练样本，故效率偏低，且容易陷入局部最优解，因此提出了随机梯度下降算法。其每轮计算的目标函数不再是全体样本误差，而仅是单个样本误差，即每次只代入计算一个样本目标函数的梯度来更新权重，再取下一个样本重复此过程，直到损失函数值停止下降或损失函数值小于某个可以容忍的阈值。此过程简单，高效，通常可以较好地避免更新迭代收敛到局部最优解。其迭代形式为

                                                             （3）

其中是步长，步长序列为。是指与相关的一个的取值，。随机梯度是真实梯度的无偏估计。随机梯度下降算法的迭代成本独立于n，且可实现次线性收敛速度

                                       

这里的期望取决于。因为算法只能通过对目标梯度的无偏估计才能接近函数本身，故这个收敛速度对于强凸优化问题是最优的[2]。

2.3随机平均梯度下降算法（SAG）

虽然避开了运算成本大的问题，但对于大数据训练而言，SG效果常不尽如人意，因为每一轮梯度更新都完全与上一轮的数据和梯度无关。随机平均梯度算法克服了这个问题，在内存中为每一个样本都维护一个旧的梯度，随机选择第个样本来更新的梯度此样本的梯度，其他样本的梯度保持不变，然后求得所有梯度的平均值，进而更新了参数.如此，每一轮更新仅需计算一个样本的梯度，计算成本等同于SG，但收敛速度快得多[2]。其迭代形式为

                                                                 （4）

每次迭代都随机选择训练样本，样本序号为，且有

                                       

 

2.4小批量梯度下降算法（mini-bantch）

小批量梯度下降算法是FG和SG的折中方案,在一定程度上兼顾了以上两种方法的优点。每次从训练样本集上随机抽取一个小样本集，在抽出来的小样本集上采用FG迭代更新权重。被抽出的小样本集所含样本点的个数称为batch_size，通常设置为2的幂次方，更有利于GPU加速处理[7]。特别的，若batch_size=1，则变成了SG；若batch_size=n，则变成了FG.其迭代形式为

                                                              （5）

其中代表所选批次的batch_size，表示所选批次的第个样本点的损失函数。

在实际操作中，常将全体训练样本集随机分组，每组样本数量相等，一般为每组10～100个样本，随机抽取其中一组，组内使用FG使得权值更新，至此称为完成一轮更新。然后重新随机分组，继续下一轮更新，一般迭代更新30～200轮[8]。每完成一轮迭代，可以将步长乘一个小于1的常数，使学习率逐渐变小，对避免局部最优解有一定效果。

3实验

3.1模型建立

为了比对四种基本梯度下降算法的性能，我们通过一个逻辑二分类实验来说明。本文所用的Adult数据集来自UCI公共数据库（http://archive.ics.uci. edu/ml/datasets/Adult）。数据集共有15081条记录，包括“性别”“年龄”“受教育情况”“每周工作时常”等14个特征，数据标记列显示“年薪是否大于50000美元”。我们将数据集的80%作为训练集，剩下的20%作为测试集，使用逻辑回归建立预测模型，根据数据点的14个特征预测其数据标记（收入情况）。

建立预测模型

                                            （6）

 

其中，y为数据标签，y=1表示“年收入大于50000美元”，y=0表示“年收入小于等于50000美元”。表示14个特征数据，为模型参数，也是我们要训练的目标参数。由于逻辑回归的极大似然函数越大代表回归效果越好，故使用负的极大似然函数做为损失函数，即

                                                    （7）

目标函数为

                                                                       （8）

3.2实验结果及分析

使用python软件对以上数学模型进行编程，在参数更新环节分别使用FG,SG,SAG和mini-batch.以下6幅图反映了模型优化过程中四种梯度算法的性能差异。

 

在图1和图2中，横坐标代表有效迭代次数，纵坐标代表平均损失函数值。图1反映了前25次有效迭代过程中平均损失函数值的变化情况，为了便于观察，图2放大了第10次到25次的迭代情况。从图1中可以看到，四种梯度算法下，平均损失函数值随迭代次数的增加而减少。FG的迭代效率始终领先，能在较少的迭代次数下取得较低的平均损失函数值。FG与SAG的图像较平滑，这是因为这两种算法在进行梯度更新时都结合了之前的梯度；SG与mini-batch的图像曲折明显，这是因为这两种算法在每轮更新梯度时都随机抽取一个或若干样本进行计算，并没有考虑到之前的梯度。从图2中可以看到虽然四条折现的纵坐标虽然都趋近于0，但SG和FG较早，mini-batch最晚。这说明如果想使用mini-batch获得最优参数，必须对其进行较其他三种梯度算法更多频次的迭代。

在图3，4，5，6中，横坐标表示时间，纵坐标表示平均损失函数值。从图3中可以看出使用四种算法将平均损失函数值从0.7降到0.1最多只需要2.5s，由于本文程序在初始化梯度时将梯度设为了零，故前期的优化效果格外明显。其中SG在前期的表现最好，仅1.75s便将损失函值降到了0.1，虽然SG无法像FG那样达到线性收敛，但在处理大规模机器学习问题时，为了节约时间成本和存储成本，可在训练的一开始先使用SG，后期考虑到收敛性和精度可改用其他算法。从图4，5，6可以看出，随着平均损失函数值的不断减小，SG的性能逐渐反超FG，FG的优化效率最慢，即达到相同平均损失函数值时FG所需要的时间最久。当平均损失函数值达到时FG，SG，SAG，mini-batch所需的时间分别为：25.2s，17.7s，18.2s，18.5s。

综合分析六幅图我们得出以下结论：（1）FG方法虽然在模型训练过程中迭代次数最多，但由于它每轮更新都要使用全体数据集，故花费的时间成本最多，内存存储最大。（2）SAG在训练初期表现不佳，优化速度较慢。这是因为我们常将初始梯度设为0，而SAG每轮梯度更新都结合了上一轮梯度值。（3）综合考虑迭代次数和运行时间，SG表现性能都很好，能在训练初期快速摆脱初始梯度值，快速将平均损失函数降到很低。但要注意，在使用SG方法时要慎重选择步长，否则容易错过最优解。（4）mini-batch结合了SG的“胆大”和FG的“心细”，从6幅图像来看，它的表现也正好居于SG和FG二者之间。在目前的机器学习领域，mini-batch是使用最多的梯度下降算法，正是因为它避开了FG运算效率低成本大和SG收敛效果不稳定的缺点。

4几种优化梯度算法

基于四种基本的梯度下降算法，许多研究者结合一些新思想，提出了几种优化梯度算法。

4.1动量（Momentum）

其迭代形式为：

其中是一些确定的数，是惯性造成的冲量[9]。在峡谷地区（某些方向较另一些方向上陡峭的多，常见于局部极值点），SG方向会在这些地方附近震荡，从而导致收敛速度变慢，加动量项法就可解决这个问题。在更新模型参数时，对于那些当前梯度方向与上一次梯度方向相同的参数，应进行加强，即在这些方向上更快了，否则进行削减。因此可获地更快的收敛速度，减少震荡。动量法可以提高实际性能，它需要一个递减的步长序列，但在理论上目前还未证明它的收敛速度更快。

SG可用动量方法改写为：

                                                                             （9）

SAG可用动量方法改写为：

                                                             （10）

 

4.2梯度平均(GrandientAveraging)

其迭代形式为：

                                                                  （11）

这个形式与SAG的（4）式相似，但它使用了之前所有求得的梯度[10]。这种方法对于一些固定步长可以达到收敛效果，也可以在一定程度上提升收敛速度，但未能超过[11]

4.3迭代平均(IterateAveraging)

其迭代形式为：

                                                        （12）

梯度平均法将前面所有迭代的前进方向（梯度）求平均，而迭代平均法则是将前面所有点的位置求平均[12][13][14]。

4.4FG的随机版本(StochasticVersionsofFGMethod)

对于光滑函数，有许多可用的方法可以加快FG的收敛速度，比如加速全梯度法(AFD)和加速随机梯度法(AGD)，他们将收敛速度分为确定和不确定的两个部分，在基于二次逼近的经典技术比如非线性共轭梯度法和类牛顿法的帮助下，可以提高确定部分的可靠性[15][16]。

4.5固定步长(ConstantStepSize)

如果SG迭代使用一个固定步长（而不是一个递减的步长序列），那么收敛速度可被分为两部分。第一部分依赖于K，并线性收敛到0.第二部分独立于k，且无法收敛到0.事实上，伴随固定步长的SG方法只能在极强的假设下达到收敛，这种假设是之间的某种关系。这与SAG形成了对比，SAG可使用固定步长达到最优解，并可在没有附加假设的情况下达到线性收敛[17][18]。

4.6加速方法(AcceleratedMethods)

它在使用固定步长的同时吸取了SG方法快速收敛的特点。特别的，此方法在默认情况下使用固定步长，只有当连续两轮梯度的内积为负时才减少步长。这使得他可能会实现周期性的线性收敛，但从全局来看仍是次线性的[19][20]。

4.7混合方法(HybridMethods)

一些作者寻求从SG到FG的转化，以实现线性收敛。Bertsekas提出按照一些特殊的权重循环使用数据，从而在二次强凸函数上实现线性收敛。近期提出的另一种策略是，在函数集上选出一些作为函数批次，随着迭代的进行，函数批次的规模增大，在这些批次上使用SG方法，将一个批次内的均值作为本轮最终取值[21]。

4.8增量聚合梯度(IncrementalAggregatedGradient)

IAG算法与SAG算法相似，区别在于，IAG对于样本函数序号的选择是顺序的，而SAG则是随机的。在实际实验中，IAG的表现与FG相似，SAG优于它们[22]。

 张润,王永滨.机器学习及其算法和发展研究[J].中国传媒大学学报(自然科学版),2016,23(02):10-18+24.LeRouxN,SchmidtMW,BachFR.AStochasticGradientMethodwithanExponentialConvergenceRateforFiniteTrainingSets[C]//NIPS.2012:2672-2680.NgA．Machinelearning［EB/OL］．(2014):http://openclassroom．stanford．edu/MainFolder/CoursePage．php?course=MachineLearning．C.H.Teo,Q.Le,A.J.Smola,andS.V.N.Vishwanathan.Ascalablemodularconvexsolverforregularizedriskminimization.KDD,2007.M.A.Cauchy.M´ethodeg´en´eralepourlar´esolutiondessyst`emesd’´equationssimultan´ ees.Comptesrendusdess´eancesdel’Acad´emiedessciencesdeParis,25:536–538,1847.Y.Nesterov.Introductorylecturesonconvexoptimization:Abasiccourse.Springer,2004.LiM,ZhangT,ChenY,etal.Efficientmini-batchtrainingforstochasticoptimization[C]//Proceedingsofthe20thACMSIGKDDinternationalconferenceonKnowledgediscoveryanddatamining.ACM,2014:661-670.DudaRO，HartPE．Patternclassificationandsceneanalysis［M］．Boston:Wiley，1973．P.Tseng.Anincrementalgradient(-projection)methodwithmomentumtermandadaptivestepsizerule.SIAMJournalonOptimization,8(2):506–531,1998.Y.Nesterov.Primal-dualsubgradientmethodsforconvexproblems.Mathematicalprogramming,120(1):221–259,2009. L.Xiao.Dualaveragingmethodsforregularizedstochasticlearningandonlineoptimization.JournalofMachineLearningResearch,11:2543–2596,2010.B.T.PolyakandA.B.Juditsky.Accelerationofstochasticapproximationbyaveraging.SIAMJournalonControlandOptimization,30(4):838–855,1992. H.J.KushnerandG.Yin.Stochasticapproximationandrecursivealgorithmsandapplications.Springer-Verlag,Secondedition,2003. E.HazanandS.Kale.Beyondtheregretminimizationbarrier:anoptimalalgorithmforstochasticstrongly-convexoptimization.COLT,2011. Y.Nesterov.AmethodforunconstrainedconvexminimizationproblemwiththerateofconvergenceO(1/k2).DokladyANSSSR,269(3):543–547,1983.N.N.Schraudolph.Localgainadaptationinstochasticgradientdescent.ICANN,1999.A.NedicandD.Bertsekas.Convergencerateofincrementalsubgradientalgorithms.InStochasticOptimization:AlgorithmsandApplications,pages263–304.KluwerAcademic,2000.M.V.Solodov.Incrementalgradientalgorithmswithstepsizesboundedawayfromzero.ComputationalOptimizationandApplications,11(1):23–35,1998. H.Kesten.Acceleratedstochasticapproximation.AnnalsofMathematicalStatistics,29(1):41–59,1958.B.DelyonandA.Juditsky.Acceleratedstochasticapproximation.SIAMJournalonOptimization,3(4):868–881,1993. M.P.FriedlanderandM.Schmidt.Hybriddeterministic-stochasticmethodsfordatafitting.SIAMJournalofScientificComputing,34(3):A1351–A1379,2012. D.P.Bertsekas.Anewclassofincrementalgradientmethodsforleastsquaresproblems.SIAMJournalonOptimization,7(4):913–926,1997.