优化算法系列（2）：深入讨论SGD及其改进思路

从机器学习角度来看，一个完整的任务包括模型、评估、优化，本系列谈的就是优化。机器学习模型的训练其实就是参数学习，通常是通过一定的优化算法来寻找一组可以最小化结构风险的参数。而最常见的优化算法是梯度下降算法（SGD），基于SGD可以引申出很大的优化算法。本系列打算探讨优化算法的改进与变化逻辑。

首先来说说最基本的梯度下降（GD）算法。

梯度下降

简单回顾一下上篇说的梯度下降算法。假设有训练样本集$ D = { (x_{1}, y_{1}), …, (x_{n}, y_{n}) } $，单个样本可以用 $\boldsymbol{x}=(x,y)$来表示，模型$f_{\theta}(x)$的优化参数为 $\theta$ ，那么整个训练样本集上的损失函数为

$$\begin{align} L(\theta) = \frac{1}{\left | D \right |} \sum_{(x,y) \in D}L(y,f_{\theta}(x)) \end{align}$$

为完成优化目标，GD的做法是

$$\begin{align} \theta_{n+1} = \theta_{n} - \gamma \nabla_{\theta}L(\theta_{n}) \end{align}$$

我们这里不讨论起导出。其中$0 \lt \gamma \ll 1$称为学习率。注意到，每次迭代时，GD都要运用整个训练集D来进行梯度计算，对于数据量小的情况可以接受，但是在训练神经网络时，这个计算量就十分巨大。

于是随机梯度下降（SGD）就来解决这个问题，每次随机采样一个批量来替代全批量作为梯度计算的数据。

随机梯度下降

随机梯度下降的随机来自哪里？那就是随机采样定量样本来估计梯度替代全量数据的梯度。

SGD的随机性

与GD每次都用全量的数据不同，SGD每次只取其子集$R_{i}\subseteq D$来计算梯度，于是有

$$\begin{align} L_{R_{i}}(\theta) = \frac{1}{\left | D \right |} \sum_{(x,y) \in R_{i}} L(y,f_{\theta}(x)) \end{align}$$

子集$R_{i}$称为批，其大小称为批量，就是我们训练神经网络常用的参数batch_size。由于$R_i$是随机采样自$D$，因此$L_{R_{i}}(\theta)$也是一个随机变量。

SGD迭代过程，

$$\begin{align} \theta_{n+1} = \theta_{n} - \gamma \nabla_{\theta}L_{R_{i}}(\theta_{n}) \end{align}$$

由于$L_{R_{i}}(\theta)$是一个随机变量，所以$\nabla_{\theta}L_{R_{i}}(\theta_{n})$也是一个随机变量，是原来真是梯度$\nabla_{\theta} L(\theta_n)$​的估计。因此，可以看到，随机梯度下降的随机就体现在对梯度的计算的随机性上。不严格来说，在实践中，学习率会随着模型的训练进度而调整，因此学习率$\gamma$本身也是SGD中随机的来源。

原来我们是用整个训练集来计算梯度，现在我们是在训练集的子集上计算（估算）梯度，那么它们之间的差肯定为一个随机数，即

$$\begin{align} \nabla_{\theta} L(\theta) - \nabla_{\theta} L_{R_{i}}(\theta) &= \xi_{i} \end{align}$$

$\xi_{i}$ 表示批次$i$在子集样本$R_{i}$​上的梯度误差，这个误差我们可以从方差的角度来衡量，

$$\operatorname{Var}(\xi_i) = \sigma_i^{2}$$

如果要把$\gamma \nabla_{\theta}L_{R_{i}}(\theta_{n})$当做一个正态考虑，那么

$$\operatorname{Var}(\xi_i) = \gamma^2 \sigma_i^{2}$$

尽管随机采样带来梯度计算的误差，但从优化角度看也带来一个好处。梯度下降（GD）在鞍点处梯度为0，一点陷入鞍点难以逃离，而随机梯度下降（SGD）相比与梯度下降（GD）引入随机性能够有利于逃离鞍点。

批量大小的选择

不难理解，假定学习率不变的情况下，当集样本$R_{i}$的数量越大，梯度误差$\xi$的方差越小，引入的噪声越小，反之则相反。我们可以想象两个极端，当集样本$R_{i}$为整个训练集时，GD和SGD的梯度没有差别，当集样本$R_{i}$每次只取一个样本时，GD和SGD的差别是最大的。

这个思考给我们的启示是，在训练模型时，假定学习率不变的情况下，当选择更小的批量时，计算效率快，但梯度误差的方差更大，训练不稳定，更难收敛，当选择更大的批量时，梯度误差的方差更小，有利于训练稳定，有利于快速收敛（不能保证收敛得更好），但需要的计算资源更大。

但是batch size参数的随意增加会加大计算成本，同时也考虑到$\operatorname{Var}(\xi_i) = \gamma^2 \sigma_i^{2}$，从调整学习率的角度来调整梯度误差的方差更合理。从实践的角度来看，批量大小一般是增加都一定大小后就不再增加，如32，64， 128，然后把关注点转向对学习率的调整。

学习率调整与warm-up

直观上看，随着SGD的迭代，

$$\begin{align} \theta_{n+1} = \theta_{n} - \gamma \nabla_{\theta}L_{R_{i}}(\theta_{n}) \end{align}$$

靠近极小值时，$\nabla_{\theta}L_{R_i}(\theta_{n})$​取值很小，导致更新速度减慢，这个时候学习率$\gamma$也应该相应的减小，避免$\theta$在一个狭小的区间内反复横条，影响收敛速度。

此外，我们还有考虑学习率与batch_size同步的问题，根据Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour，学习率在批量大小比较小的时候，按线性缩放。就是说在一定范围的批量大小内，当批量翻倍时，学习率也应该翻倍。

SGD的简单分析

与其他的数值优化算法一样，随机梯度下降往往收敛都局部最优甚至是鞍点，如何保证泛化能力？我们来分析一下，假设在某一维度上的梯度为零的概率为p，那么局部最小的概率为$p^{n}$，这里假设参数的个数为$n$，因此，优化时找到局部最优点也是很难。也就是说更多的时候是收敛到鞍点。那么该如何保证泛化能力？

我认为这里有一个认知上的误区，就是收敛到最优点才能保证泛化能力。事实上，纯粹的数值优化问题与基于统计学习的优化在目标上不同。我们训练的目标并不是loss最优，它只不过是给我们的模型提供一个优化方向。我们的模型的实用性关注的是在测试集上某个性能指标表现很好。

因此，这个疑问在神经网络没有多大的讨论价值，当然在凸优化中有。因为在神经网络中，我们是面向测试集的某个优化指标去。另外还要考虑测试集和训练集的概念漂移以及迁移学习，从工程上看，“差不多”的就是最好的。

随机梯度下降的改进思路

以上我们获得随机梯度下降，

$$\begin{align} \theta_{n+1} = \theta_{n} - \gamma \nabla_{\theta}L_{R_{i}}(\theta_{n}) \end{align}$$

可以看到，影响 SGD 有四个因素，因此可以从这些因素上改进：

• 学习率 $\gamma$ 的调整
• 参数更新方向 （不止梯度方向）
• 批量 $R_{i}$ 的大小batch_size与梯度估计
• 提高价数（即止于计算梯度）

也就是说, 优化 SGD 可以从以上四点入手，如果调整点能让算法收敛更快、更好、更稳定, 那么就是有效的。后续我们会依据这一思路来展开讨论。

对于第四点，提高价数，考虑多元极值，Hessian矩阵

$$\displaystyle \mathbf {H} _{ij}=\frac {\partial ^{2}f}{\partial x_{i}\partial x_{j}}$$

考虑到函数的$n$次连续性，

$$\displaystyle \frac {\partial ^{2}f}{\partial x_{i}\partial x_{j}}=\frac {\partial ^{2}f}{\partial x_{j}\partial x_{i}}$$

那么Hessian矩阵是$n\times n$的对称矩阵。驻点为极值点要求Hessian矩阵为正定矩阵，即满足$\boldsymbol{x}^{\top} \mathbf {H}\boldsymbol{x} \gt 0$​​。但是这个计算太难了，计算效率不高，因此高价数的优化算法在深度学习中很少使用。因此在接下来的文章中不考虑提高价数这一改进思路。此外，模拟退火、遗传算法、蚁群算法等，它们不能在深度学习上流行的大概率原因还是计算效率。

其他

SGD优化器对神经网络参数更新时可以简单写成，

$$w_{i+1} = w_i + \varepsilon$$

所有其他的优化算法都是这种形式。这种形式其实就是类似随机漫步（随机游走），也就是说参数的更新过程可以看做是带约束的随机游走。那么，神经网络的优化是否可以使用随机过程刻画，并利用随机过程的一些性质探索神经网络训练的特点呢？

作为一个问题留作思考。

总结

抛开机器学习来看，在应用数学上有很大的优化算法，如粒子群优化算法、模拟退火算法，然而这类算法在训练模型上不常使用，我个人的理解是效率问题。往往工程落地和纯粹的理论之间是有一定的差别的，工程落地考虑到业务本身的约束会愿意在理论上作妥协。本篇讲述SGD，是训练神经网络最常用的优化算法，效率高，因而在工程上大量使用。

参考

[1] 《数值分析》