How does mini-batch size affect the performance of SGD?

一、概述

本文记录了自己探究batchSize, lr以及Performance之间关系这一问题时做的笔记，组织比较无序。第二、三部分为当时的问题和解答。第四部分为两篇论文的笔记。最后一部分给出了探究结果的其实——训练神经网络时和batchSize以及lr相关的trick。

顺便说下，本文一些重要的参考文献是Quora, reddit等国外高质量论坛的帖子。如果你需要访问，务必小心，因为有一定几率接到“擅自建立，使用非法定信道进行国际联网”的通知~

二、问题陈列：

batchSize越小，训练过程的随机性（不确定性）越高，即训练过程中梯度包含的噪声更多，或者说minibatch的梯度具有越高的方差，进而得出结论，Small batchSize方法具有更好的“探索性”。上述说法只是直觉层面，有无理论证明？
为什么batchSize越大，网络收敛越慢？在一定范围内batchSize越大，GPU的并行效率不是越高吗？batchSize和学习率的关系？
为什么batchSize大到一定程度以后，validation performance大幅下降？
应该如何理解optimization过程中的minimizer？

三、答案：

【更新】：下面的答案有几处不严格的地方：
参考Ian本人的答案：
https://www.quora.com/In-deep-learning-why-dont-we-use-the-whole-training-set-to-compute-the-gradient

答案2中说：“100-batch和10000-batch相比，前者的梯度方差是后者的100倍”。这个应该是不对的。不过计算量确实是线性关系。见下面截图：

Update 1. Ian回答截图 1
并不是训练时使用整个训练集（即batchSGD）就能获得“clean gradient”。真实的梯度应该是在所有可能的样本点上计算出的梯度，在数据生成分布上的加权和。使用整个训练集只是相当于用一个很大的minibatch size。见下图：

Update 2. Ian回答截图

尝试解答：

答：【严格证明有待补充】我们在使用mini-batch SGD训练NN时，实际上做的事情，是通过mini-batch上的梯度来估计整个训练集上的梯度。显然，使用1个样本（即SGD）相比使用100个样本的batch，梯度的噪声要大得多。也就是说，当使用小batch SGD时，我们并不总是沿着loss下降最快（即梯度方向）的方向移动的。相反，如果使用整个数据集作为训练集（batch SGD），那么我们训练时的梯度是非常"clean"的，这样会导致一个问题：优化过程将卡在第一个local minima处。因为此时梯度值为0。

答：考虑我们有个包含100, 0000个训练样本的数据集。我们考虑两种方法：batchSize为100和10000的算法来训练神经网络，假设使用相同的step size（即学习率）。大体上，梯度计算的复杂度和batchSize成线性关系。故计算10000-batch的梯度的时间，大约为计算100-batch梯度时间的100倍。
这意味着在10000-batch更新参数一步的时间(one step update)，100-batch方法可以更新100步参数。由于mini-batch SGD算法参数更新不一定沿着梯度方向（即1中所答），这100个更新steps的“成效”肯定达不到10000-batch那一步更新的100倍。但是至少也能达到10倍以上的“成效”。这就是为什么mini-batch SGD算法要比batch SGD节省大量时间。
注意，刚才我们的假设是100-batch和10000-batch使用相同的学习率。现在我们考虑另一个问题：batchSize和学习率的关系。由于large-batch方法训练时梯度的方差更小，或者说由于loss下降的方向更严格地沿着梯度方向，我们可以选择更大的batchSize。具体来说，100-batch和10000-batch相比，前者的梯度方差是后者的100倍。理论上这使得我们可以用100倍的学习率来训练，这样的话，理论上我们用10000-batch更新1步的速度其实和100-batch更新100步的速度相同。如果是这样的话，那将是非常理想的。因为大的batchSize会更大程度利用GPU的并行运算能力，极大的提高训练效率。然而事实上，尽管我们可以对larger batch使用更大的学习率，但是这个学习率是有一个上限的。"the step-size cannot exceed an algorithmic, problem-dependent upper bound which depends on the smoothness of the objective function (typically 1/L, where L is the Lipschitz constant of the "full" gradients)"

参考：https://www.quora.com/Intuitively-how-does-mini-batch-size-affect-the-performance-of-stochastic-gradient-descent

答：因为"large-batch methods tend to converge to sharp minimizers of the training and testing functions，而sharp minima lead to poorer generalization"。至于为什么sharp minima导致泛化更差？见Fig. 1。
答：就是loss surface上不同的局部极小值点。有的极小值点附近比较陡，有的比较平坦。参考论文：Visualizing the Loss Landscape of Nural Network中摘要第一句话：
Neural network training relies on our ability to find “good” minimizers of highly non-convex loss functions.

四、论文笔记

篇1：On Large-Batch Training for DL——Gerneralization Gap and Sharp Minima

现象：较大的batchSize(LB methods)会导致验证集表现和训练集表现出现明显鸿沟（训练集表现没有影响）。
推测：①LB导致模型过拟合②LB方法容易陷入鞍点③LB缺乏SB的“探索性质”（即SB的引入的随机性使得优化过程有一定几率跳过local minima）④SB和LB方法会收敛到具有不同泛华性质的不同的minimizer。
本文可以证明，后两个推断是合理的。
名词解释：
①minimizer与minima：~~minimizer本质是function，而minima是minimizer函数值最低点对应的X(parameters）取值。一个在邻域内变化很小的函数被称为flat minimizer，反之则是sharp minimizer。~~minimizer和minima这里应该是相同的意思，指局部极小值点。为什么minimizer sharp了泛化就差？解释如下：
解释一：flat minimum只需要用比较低的精度就能描述；sharp minimu需要非常精确的描述。根据MDL(minimum description length)理论，states that statistical models that
require fewer bits to describe (i.e., are of low complexity) generalize better。或者更直观地，精确的minimu会导致最优点高度敏感，见下图：

Fig. 1. flat and sharp minimizer的不同泛化能力

②sharpness：直观的解释见上图。作者也选择了一个客观指标来衡量sharpness：理论上最好的指标是" 目标函数f的海森矩阵的模"。然而海森矩阵计算量太大。故选取了一个近似指标：目标函数f在某个小邻域范围中可以取得的最大的函数值。
什么是SB方法的“探索性”？
答：SB方法中，梯度中固有的噪声会push参数更新过程，让其远离sharp minimizers（~~这里不要把minimizer看成全局的。可以理解为不同的局部有不同形状的minimizer~~这里的minimizers应该是说，在一个很大的function set(取决于model capacity)中，有一些function是sharp minimizers，另一些是flat minimizers，然后模型最终的优化只会选择其中一个function。可以这样理解吗 这里的minimizers是指loss surface上不同的局部极小值点），并且倾向于陷入即使是噪声也无法让优化过程跳出的，更平坦的局部极小值。因此，超过一个阈值之后，继续增大BatchSize会导致梯度噪声的减小，这样优化过程就无法跳出那些原本可以跳出的，比较sharper的局部极小值。
warm-start
在上述分析的基础上，作者设置了一个实验：

Fig. 2. warm-start实验的设计

注意：这个实验非常重要。作者用小batchSize (SB)和ADAM train了100个epoch，并且将每个100个的训练结果保存下来。然后使用每一个保存的断点，换成大的batchSize继续训练100个epoch，这样得到100个warm-started LB solutions。作者比较了这一百个结果，发现如下的规律：

在继承最开始的几个epoch训练的LB模型未表现出泛化性能的提升。与此同时这些模型对应的sharpness维持在较高的水准。然而在经过一定epoch数的warm-starting之后，LB模型的泛化性能显著提高，同时sharpness下降。也就是说：The SB method has ended its exploration phase and discovered a flat minimizer.

Fig. 3. warm-start: 先使用SB train 几个epoch，然后换成LB

其他实验：本文还做了一些其他实验试图减小LB的sharpness，比如数据增强，甚至一些对抗方法。然而这些方法，虽然一定程度上提高了泛化性能，但是并没有降低模型的sharpness。故作者认为这些方法并没有解决问题。

篇2 DON’T DECAY THE LEARNING RATE, INCREASE THE BATCH SIZE

首先要强调一下，这篇文章，还有facebook那篇 Training ImageNet in 1 Hour面向的问题差不多，基本上是超过8个GPU，分布式大规模计算的情景，解决增大batchSize网络模型变差这样问题。不过其中的场景和我们实验室的差别较大，可能其中有很多有用的tricks，但是目前可能还用不上...这里就把两篇论文中感兴趣的points整理在一起：

1. Linear Scaling Rule
  
  Fig. 6. Linear Scaling Rule
  
  然而知乎上有人提出了自己的实践经验，就是说对于异步SGD，这个Linear Scaling Rule不太适用。
  
  Fig. 7. 知乎上有人提出的质疑

很多人说facebook这篇文章提出的tricks很实用，不过由于时间原因还没仔细了解，因为我觉得可能当前阶段李沐的tricks学习优先级更高一些。以后如果有幸能参与大规模集群开发，再好好学一学facebook的expensive experiment tricks...

1. noise scale
  Google这篇文章中大量使用了Smith & Le论文（看了下，原来是自己的文章...）中提出的一个概念：noise scale。即下图的公式：

Fig. 8. noise scale

由这个式子，作者认为衰减学习率其实和增大BatchSize拥有相同的效果（在满足N<<B的前提下）。作者在文章中使用不同的training schedule，比如只衰减学习率；只增大batchSize或者两者混合进行。最终的结果是得到了几乎一致的训练曲线。故作者得出结论：与模型表现真正相关的不是学习率，而是noise scale。因为这几组实验真正在做的事情，是decay noise scale。

1. 模拟退火

本文提出的一个重要概念：将神经网络训练过程类比为物理科学中的模拟退火，其中的“火”指的是温度，而对应到神经网络中则是噪声幅度，即 2 中的noise scale。以下为详细分析：

①本博客上面提到，LB方法具有一定探索性，因为其梯度噪声较大。而随着训练过程接近optima，我们必须逐渐减小学习率以抵消梯度的bounce。显然这符合上面描述的逐渐减小noise的过程。注意这也正是我们常用的策略。因为我们的GPU资源有限，其实batchSize也增大不了多少。
另外一个非常有趣的事实是，研究者们越来越不倾向于使用较温和的学习率衰减策略，如平方根或者指数衰减，而倾向于使用sharper的策略，如cosine decay或者step-functions decay。作者认为也可以使用物理科学中的模拟退火现象来类比：

To interpret this shift, we note that it is well known in the physical sciences that slowly annealing the temperature (noise scale) helps the system to converge to the global minimum, which may be sharp. Meanwhile annealing the temperature in a series of discrete steps can trap the system in a “robust” minimum whose cost may be higher but whose curvature is lower. We suspect a similar intuition may hold in deep learning.

②另一个角度来说，batchSize越大，梯度噪声越小。通过逐步增大batchSize达到模拟退火的效果。

③上面两点本质上都是在通过减小训练过程中的noise scale来实现模拟退火。训练初期使用较大的噪声，允许模型在一个更大的参数空间中探索，而不会轻易卡在local minima；经历过这一阶段之后，我们可以在一个局部的，更有前景的参数空间中减小noise，并微调我们的参数。见原文中的论述：

Fig. 9. 原文中针对模拟退火的描述

注意，这个描述高度符合篇一中warm-start实验的做法。

1. 有效学习率，momentum系数与训练启动期

这部分中比较有意思的是，作者通过推理给出了noise scale公式的momentum版本。进而提出了两个概念：有效学习率和 $N_{lost}$ 。我们可以简单看下推导：

Fig. 10. 带momentum的noise scale推导

由于accumulate variable $A$ 被初始化为0， $delta A$ 在前几个epoch一致很小，从而导致参数更新幅度 $deltaW$ 被抑制。直到经过一定数目epoch，才能进入稳定的训练阶段。作者后面继续推导，找到了这个训练初期的epoch数目， $N_{lost} = B/(N(1-m))$ 。并给出了后续结论：