【梯度下降法优化】随机梯度下降、牛顿法、动量法、Nesterov、AdaGrad、RMSprop、Adam

本文理论参考王木头的视频：

“随机梯度下降、牛顿法、动量法、Nesterov、AdaGrad、RMSprop、Adam”，打包理解对梯度下降法的优化_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1r64y1s7fU/?spm_id_from=333.999.0.0&vd_source=ecbdfcacb078d0e3626e61248866cdc7

标准梯度下降公式：

假设我们有一个函数 $f(\theta)$ ，其中 $\theta$ 是待优化的参数。梯度下降法的迭代更新公式为：

$\theta = \theta - \alpha \nabla f(\theta)$

其中：

$\alpha$ 是学习率（learning rate），表示每次迭代的步长；
$\nabla f(\theta)$ 是函数在 $\theta$ 处的梯度，即偏导数。

标准的梯度下降法要求每次迭代都要考虑所有的样本数据，计算量很大，在大部分问题中都要对其进行优化，优化梯度下降法有两个思路：

（1）调整神经网络的结构，比如说增加池化层、用Dropout方法等。

（2）在梯度下降法公式本身上进行优化。

本文只关注上述第二类优化思路，优化梯度下降公式。

对梯度下降公式进行优化可以从两个方面出发，一是改变每次迭代的样本数，如随机梯度下降、小批量梯度下降（min-batch）等；二是优化下降路径。这里有一个疑问？梯度下降法的路径已经是梯度下降最快的路径了，那么路径还有优化的必要吗？要从哪个方面优化路径呢？我们知道梯度是一个点上下降最快的方向，画在图上是按照线段下降的，所以还会有误差，怎么优化呢，显然把这个线段变短（即减小学习率）是一种优化方式，但会使得问题更加复杂。另一种方法是把这个线段变成更符合高维曲面曲线。具体怎么做呢？下面有详细分析。

二、随机梯度下降法

1、定义

随机梯度下降法公式为：

假设我们有一个损失函数 $f(\theta) = \frac{1}{N} \sum_{i=1}^{N} f_i(\theta)$ ，其中 $N$ 是样本数量， $\theta$ 是模型参数。随机梯度下降的更新公式为：

$\theta = \theta - \alpha \nabla f_i(\theta)$

其中：

$\alpha$ 是学习率，控制每次更新的步长；
$\nabla f_i(\theta)$ 是基于第 $i$ 个样本计算的梯度。

不同于批量梯度下降（一次使用所有样本计算梯度），随机梯度下降在每一步只使用一个样本计算梯度，这使得算法在处理大规模数据时更加高效。

2、思考

一次只选一个样本进行梯度下降，可以达到最优点吗？

数学上对这个问题进行了证明，证明结果如下：

对于凸问题：

这个公式的意思是：迭代 $k$ 次后，误差的量级为 $\frac{1}{\sqrt{k}}$

对于强凸问题，收敛速度会更快：

每次迭代只选一个样本的随机梯度下降法用的比较少，一般使用小批量梯度下降。

三、小批量梯度下降法

假设我们有一个损失函数 $f(\theta) = \frac{1}{N} \sum_{i=1}^{N} f_i(\theta)$ ，其中 $N$ 是样本数量， $\theta$ 是模型参数。设定小批量大小为 $m$ ，那么小批量梯度下降的更新公式为：

$\theta = \theta - \alpha \frac{1}{m} \sum_{j=1}^{m} \nabla f_{i_j}(\theta)$

其中：

$\alpha$ 是学习率；
$\{i_1, i_2, \ldots, i_m\}$ 表示从样本集中随机选择的一个小批量样本索引；
$\frac{1}{m} \sum_{j=1}^{m} \nabla f_{i_j}(\theta)$ 是基于小批量样本计算得到的平均梯度。

四、牛顿法

1、理解

牛顿法是优化梯度下降的一种方式。

王木头误我！

下面以一个小例子来体会牛顿法。

画出 $f(x)=\frac{1}{20}x^{4}-\frac{2}{5}x+1$ 如下图

在 $x_{k}$ 处开始梯度下降，梯度 $f{}'(x_{k})=\underset{x\rightarrow x_{k}}{lim}\frac{f(x)-f(x_{k})}{x-x_{k}}$ ，即在 $x_{k}$ 附近有切线 $f_{1}(x)=f(x_{0})+f{}'(x_{k})(x-x_{k})$ ，其为 $f(x)$ 在 $x_{k}$ 处的切线，在普通的梯度下降法中，我们选用这个切线作为原函数的近似值进行梯度下降，对于单调函数（切线）是没有极小值的，但需要将其约束在 $x_{k}$ 附近才有切线约等于原函数，所以就有了学习率 $\alpha$ ， $\alpha$ 越小，梯度下降的步伐越小，但效率低， $\alpha$ 越大，梯度下降地越快，但容易在极小值附近跳动，不容易收敛。

为加速收敛，以最佳方式调整 $\alpha$ ，对普通梯度下降进行优化，采用牛顿法，牛顿法是如何调整 $\alpha$ 进行梯度下降地呢？

使用泰勒展开，在 $x_{k}$ 处不仅使用一阶导数进行逼近，还使用二阶导数进行逼近，即： $f_{2}(x)=f(x_{0})+f{}'(x_{k})(x-x_{k})+\frac{1}{2}f{}''(x)(x-x_{k})^{2}$ ，逼近函数就不再是线性的，是二次函数形式的，如图中粉色曲线。

现在不再最小化 $f(x)$ ，而最小化这个二次函数 $f_{2}(x)$ ，并将二次函数的最小点作为下次迭代的起始点，易得 $f_{2}(x)$ 的最小值在 $x=x_{k}-\frac{f{}'(x)}{f{}''(x)}$ ，即这相当于 $\alpha =\frac{1}{f{}''(x)}$ 。这正是牛顿法的全部精华。使用牛顿法，我们不再手动选择步长 $\alpha$ 。

将上述例子推广到多维函数的情况：

$x_{k+1}=x_{k}-\triangledown ^{2}f(x_{k})^{-1}\cdot \triangledown f(x_{k})$

其中，

一阶导数被替换为了梯度，二阶导数被替换为了海森矩阵的逆

2、疑问

这里还有一个疑问？使用牛顿法时，学习率 $\alpha$ 取为 $\frac{1}{f{}''(x)}$ 时，会出现 $\alpha$ 过小效率低或 $\alpha$ 过大梯度无法收敛的情况吗？

（1）定性分析

牛顿法的收敛速度是二次的，即当接近极值点时，误差会以平方速率收敛。这意味着在离极值点越近时，更新步长会越来越小，使得每次迭代都能更精确地靠近极值点，而不会越过它。

牛顿法通过 Hessian 矩阵（即二阶导数矩阵）提供的曲率信息来调整步长。Hessian 矩阵的作用是确定函数在当前点的曲率，即判断该点的凹凸程度。根据曲率的大小，牛顿法能够自适应地调整步长：

在曲率较大的区域（即函数弯曲较剧烈的区域），Hessian 矩阵的逆会使得步长较小；
在曲率较小的区域（即函数较平坦的区域），步长会相对较大，但不会超过合理的范围。

这种曲率自适应调节确保了在接近极值点时，牛顿法会自动缩短步长以防止越过极值点。

牛顿法通过泰勒展开得到更新公式，实际上是寻找目标函数在当前位置的二次近似（即抛物线）的最小值。由于二次近似提供了函数在该区域内的最优步长，因此牛顿法在每次迭代时已经考虑了步长的优化，这也是它比梯度下降法收敛快的原因。

牛顿法的这种“减速”机制源于 Hessian 矩阵的自适应步长特性，使得它能够在极值点附近进行更为精细的调整。

需要注意的是，在非凸优化问题中，如果 Hessian 矩阵存在负特征值，牛顿法可能无法保证一步步接近极值点，甚至可能导致发散。然而在接近极小值点且曲率为正的情况下，牛顿法依然能有效避免越过极值点。

（2）定量证明

收敛步长分析

我们设当前的迭代点为 $\theta_k$ ，根据牛顿法的更新公式，下一步更新为：

$\theta_{k+1} = \theta_k - H^{-1} \nabla f(\theta_k)$

在极值点附近，目标函数的梯度 $\nabla f(\theta)$ 可以用泰勒展开表示：

$\nabla f(\theta_k) = H (\theta_k - \theta^*)$

因此，更新公式可以写为：

$\theta_{k+1} = \theta_k - H^{-1} H (\theta_k - \theta^*) = \theta^*$

这表明，在极值点附近，牛顿法的更新将直接达到极值点。

然而，在实际情况中，因计算误差或非理想的初始点，牛顿法不会直接收敛到极值点，而是逐渐逼近。我们可以进一步推导这种逼近的速度。

牛顿法的二次收敛性证明

为了量化牛顿法的收敛速度，我们可以定义误差向量 $e_k = \theta_k - \theta^*$ ，即迭代点 $\theta_k$ 与极值点 $\theta^*$ 之间的偏差。然后我们来看误差在每次迭代后的变化。

通过牛顿法的更新公式有：

$\theta_{k+1} - \theta^* = \theta_k - H^{-1} \nabla f(\theta_k) - \theta^*$

代入梯度的近似表达式 $\nabla f(\theta_k) = H (\theta_k - \theta^*)$ ，得到：

$e_{k+1} = \theta_{k+1} - \theta^* = \theta_k - H^{-1} H (\theta_k - \theta^*) - \theta^* = e_k - e_k = 0$

3、牛顿法的缺陷

（1）逆矩阵计算复杂

1.、解决方法有：

准牛顿法（Quasi-Newton Methods）、阻尼牛顿法、共轭梯度法、稀疏 Hessian 矩阵的利用、近似 Hessian 矩阵、信赖域方法、混合一阶和二阶方法，等；这些算法我都不懂。

（2）在负曲率的情况下，一些改进方法（如阻尼牛顿法）会引入限制，使得步长在负曲率区域自动缩小，以避免发散和过冲的问题。其次还可使用信赖域方法、共轭梯度法、混合方法：梯度下降法 + 牛顿法、修正 Hessian 矩阵，等；这些算法我都不懂。

五、动量法

1、什么是动量法

动量法，即类似于pid中的积分项，有抑制震荡、加快收敛速度的功能

梯度下降时如果出现发生震荡或学习速率慢，可采用动量法优化路径，如图

橙色线在水平维度学习速率慢，在竖直维度震荡，采用动量法优化后如图中绿色线。

2、定义和推导

动量法的核心思想是通过对梯度的加权平均（或者说对梯度的动量）来更新模型的参数。具体来说，它将梯度更新中的历史信息考虑进来，从而避免了在局部极小值和鞍点附近的振荡，并且在某些方向上能够加速收敛。

动量法的更新公式如下：

$v_{t+1} = \beta v_t + (1 - \beta) \nabla f(\theta_t)$

$\theta_{t+1} = \theta_t - \eta v_{t+1}$

其中：

$v_t$ 表示第 $t$ 次迭代的动量（即前几次梯度的累积）；
$\beta$ 是动量因子，通常设置为 0.9 或 0.99，控制历史梯度对当前更新的影响；
$\nabla f(\theta_t)$ 是当前的梯度；
$\eta$ 是学习率，控制每次更新的步长；
$\theta_t$ 是参数的当前值。

3、几何意义

几何意义：

动量法的几何意义可以通过物理学中的“惯性”来理解。假设目标函数在优化过程中存在较大的曲率变化或者平坦的区域（例如在鞍点附近）。在这种情况下，标准梯度下降法可能会因为梯度方向不稳定而产生振荡，导致无法有效收敛。

动量法的惯性允许优化过程在梯度方向上继续推动，而不是因为当前梯度的微小变化就停止。因此，在较平坦的区域，动量法能够快速移动，而在陡峭的方向上，动量法能够抑制震荡。

六、Nesterov加速梯度法

上面动量法类似于pid中的积分项，而这个Nesterov加速梯度法即是pid中的微分项。核心思想是，在进行梯度更新时，提前对未来的梯度信息进行预估，然后基于这个预估值来调整当前的参数更新方向。通过这种方式，Nesterov加速梯度法能比标准的动量法更好地利用梯度信息，从而提高收敛速度。

1、定义

NAG的更新公式可以写作：

$v_{t+1} = \beta v_t + (1 - \beta) \nabla f(\theta_t - \eta \beta v_t)$

$\theta_{t+1} = \theta_t - \eta v_{t+1}$

其中：

$v_t$ 是第 ttt 次迭代的动量（即梯度的加权平均）；
$\beta$ 是动量因子，通常取 0.9 或 0.99，控制历史梯度对当前更新的影响；
$\nabla f(\theta_t)$ 是当前点的梯度；
$\eta$ 是学习率，控制每次更新的步长；
$\theta_t$ 是参数的当前值。

七、AdaGrad优化法

其核心为自适应学习率，主要用于处理稀疏数据和高维数据。在梯度较小的维度上进行自适应放大，在梯度较大的维度上进行自适应缩小。与标准的梯度下降方法相比，AdaGrad的一个主要优势是它能够通过动态调整学习率来避免在某些方向上过快收敛（尤其是梯度较大的方向），从而提高了优化过程的稳定性。

1、定义

AdaGrad的更新公式如下：

$g_t = \nabla f(\theta_t)$

$G_t = G_{t-1} + g_t \odot g_t$

$\theta_{t+1} = \theta_t - \frac{\eta}{\sqrt{G_t + \epsilon}} \odot g_t$

其中：

$g_t$ 是当前梯度；
$G_t$ 是梯度平方和的累积（一个对角矩阵，如果是标量则为单个数值）；
$\eta$ 是初始学习率；
$\epsilon$ 是一个很小的常数，防止除零错误，通常取 $10^{-8}$ ；
$\odot$ 表示逐元素相乘。

在每次更新中，AdaGrad通过对每个参数的梯度平方进行累积，从而得到一个自适应的学习率。随着迭代次数的增加，参数更新的学习率会逐渐减小，尤其是对于那些梯度较大的方向，学习率将会迅速减小，从而有效地避免了过度更新。

2、理解

AdaGrad在训练过程中会根据每个维度的梯度历史信息动态调整学习率，避免了在每个方向上使用固定的学习率，从而可以在不同的维度上实现自适应的收敛速度。在稀疏数据中具有很大是优势，AdaGrad在稀疏数据（如自然语言处理中的词袋模型，推荐系统中的稀疏矩阵）中非常有效，因为在稀疏数据中，很多参数的梯度接近于零，这时候AdaGrad会自动增大这些参数的学习率，促进稀疏参数的学习。

3、对稀疏数据的理解

首先需要了解维度是什么，维度就是特征，这点并不难理解，当特征比较少时，即维度比较低时，两个样本的差别主要体现在特征的程度上的不同，而稀疏数据，一般伴随着高维，特征多，这种情况下，两个样本的不同主要体现在特征的种类的不同上。即，区分人和猴子时，只需区分有无尾巴或有无毛，也就是特征种类的不同（稀疏，高维），而要比较不同的人脸，则需要比较同一个特征的不同程度（非稀疏）。

随着维度的增加，遇到稀疏数据的可能性会越来越高，

有一个例子：球体的体积随维度的变化曲线为：