随机梯度下降 | 机器之心

简介

随机梯度下降（SGD）也称为增量梯度下降，是一种迭代方法，用于优化可微分目标函数。该方法通过在小批量数据上计算损失函数的梯度而迭代地更新权重与偏置项。SGD在高度非凸的损失表面上远远超越了朴素梯度下降法，这种简单的爬山法技术已经主导了现代的非凸优化。

在另一个词条“gradient descent”中我们已经介绍过梯度下降的原理，即参数依据下式更新：

当模型在每见到一组训练数据都对参数进行更新时，我们称这种梯度下降法为SGD，即如下过程：

1.初始化参数（θ，学习率$\alpha$）

2.计算每个θ处的梯度

3.更新参数

4.重复步骤2 和3，直到代价值稳定

在实际运用中，使用小批量进行参数更新的mini-batch gradient descent也常常被叫做SGD，一般我们对使用单个训练数据更新还是小批量更新不做过多区分，而主要关注算法本身。

下图给出了一个简单的一维例子，可以看到模型成功的找到了最小值：

但实际上即使对于这样简单的一维问题，学习率的选取也是很重要的。如果步长过大，则算法可能永远不会找到如下的动画所示的最佳值。监控代价函数并确保它单调递减，这一点很重要。如果没有单调递减，可能需要降低学习率。

SGD的另外一个问题其训练速度。可以想象若学习率过大，我们无法获得理想的结果，而若学习率过小，训练可能会非常耗时。对于复杂的问题，用户往往想要使用非常大的学习速率来快速学习感兴趣的参数，来获得一个初步的结果进行判断。不幸的是，当代价函数波动较大时，这可能导致不稳定。从下图可以看到，由于缺乏水平方向上的最小值，y参数方向的抖动形式。动量算法试图使用过去的梯度预测学习率来解决这个问题。

因此，目前使用的SGD往往使用动量（momentum）来缓解这个问题。通常，使用动量的SGD 通过以下公式更新参数：

γ 和ν 值允许用户对dJ(θ) 的前一个值和当前值进行加权来确定新的θ值。人们通常选择γ和ν的值来创建指数加权移动平均值，如下所示：

这种简单的改变可以使优化过程产生显著的结果，我们现在可以使用更大的学习率，并在尽可能短的时间内收敛。如下图所示，在同一个问题上，我们可以更快到达一个局部（有时是全局）最优点。

当然，SGD还有许多变体，在此我们只对最基础的进行了介绍。

[图片及描述来源：目标函数的经典优化算法介绍|机器之心]

发展历史

如上文所述，当代价函数波动较大时，SGD计算效率很低，1986年Sutton在他的论文中首先指出了这一点。1992年，Polyak等人提出平均随机梯度下降（Averaged stochastic gradient descent），是随时间记录其参数矢量平均值的随机梯度下降。1999年，Qian将动量引入了SGD中，该方法能够有效地提高稳定性、加快训练速度，目前是非常常用的一种方法。

2011年，Duchi等人提出了Adagrad算法，Adagrad是自适应梯度算法（adaptive gradient algorithm）的缩写，是一种修改后的随机梯度下降，对每个参数有单独的学习速率。

Adagrad有一个缺点，即其学习速度会快速下降，Geoff Hinton提出了RMSprop，是均方根传播（Root Mean Square Propagation）的缩写。 RMSprop将权重的学习率除以该权重近期梯度的平均值，但该算法并没有在论文中具体发表。2015年Kingma等人提出的Adam算法则是对RMSprop的改进，Adam是自适应矩估计（Adaptive Moment Estimation）的缩写，其也可以为每个参数单独指定自适应学习速率，除了存储像RMSprop之类的过去梯度的平方的指数加权平均值之外，Adam还计算过去梯度的指数加权平均值，类似于动量。Adam的表现非常优秀，在目前的研究中，若没有明确的选择偏好研究者往往会使用Adam算法。

2016年Patel提出了基于卡尔曼的随机梯度下降（Kalman-based Stochastic Gradient Descent ，kSGD），用于从伪似然模型（quasi-likelihood models）的参数学习问题，包括线性模型，非线性模型，广义线性模型和具有使用平方损失函数的神经网络。该方法对超参数不太敏感，但计算昂贵。

2018年，针对目前二阶求解器在每次迭代时需要对Hessian矩阵的近似精确求逆或使用共轭梯度法，而这个过程既昂贵又对噪声敏感的问题，João F. Henriques等学者提出了一种能直接替换当前使用的深度学习求解器的快速二阶方法。与随机梯度下降法（SGD）比，它只需要在每次迭代时进行2 次额外的前向自动微分操作，同时它的运算成本与2 次标准前向传播相当且易于实现。

	A	B	C
1	年份	事件	相关论文/Reference
2	1986	1986年Sutton指出SGD搜索的效率十分低下的缺陷	Sutton, R. S. (1986). Two problems with backpropagation and other steepest-descent learning procedures for networks. Proc. 8th Annual Conf. Cognitive Science Society.
3	1992	Polyak等人提出平均随机梯度下降（Averaged stochastic gradient descent）	Polyak, B. T.; Juditsky, A. B. (1992). Acceleration of stochastic approximation by averaging. SIAM J. Control and Optimization. 30 (4): 838–855.
4	1999	Qian将动量应用于SGD	Qian, N. (1999). On the momentum term in gradient descent learning algorithms. Neural Networks : The Official Journal of the International Neural Network Society, 12(1), 145–151.
5	2011	Duchi等人发明了Adagrad算法	Duchi, J., Hazan, E., & Singer, Y. (2011). Adaptive Subgradient Methods for Online Learning and Stochastic Optimization. Journal of Machine Learning Research, 12, 2121–2159.
6	2015	Kingma等人提出Adam算法	Kingma, D. P., & Ba, J. L. (2015). Adam: a Method for Stochastic Optimization. International Conference on Learning Representations, 1–13.
7	2016	Patel提出了基于卡尔曼的随机梯度下降	Patel, V. (2016).Kalman-Based Stochastic Gradient Method with Stop Condition and Insensitivity to Conditioning. SIAM Journal on Optimization. 26 (4): 2620–2648.
8	2018	João F. Henriques等学者提出了一种能直接替换当前使用的深度学习求解器的快速二阶方法	Henriques, J. F.(2018).Small steps and giant leaps: Minimal Newton solvers for Deep Learning.arXiv:1805.08095.

发展分析

瓶颈

这里的SGD指代传统的SGD算法，其变体如Adam等不包含在内。相比其他算法，SGD 在准确率方面有优势，然而，超参数的调优是一个难题——调整学习率设置和参数是枯燥的，也是具有挑战性的。此外，SGD在后期的更新非常慢，往往需要花费很长时间才能到达极值点。

未来发展方向

SGD的表现直接关系到神经网络等模型的训练结果，因此有关其的研究仍然是很重要的。有部分研究从SGD算法本身入手，如上面介绍的这一类SGD变体，还有一部分则提出能够提高SGD表现的其他策略，如batch normalization，early stopping的使用。

简介