深度学习笔记之优化算法(一)铺垫：梯度下降法VS最速下降法

引言

从本节开始，将介绍深度学习中常见的优化算法。在介绍随机梯度下降之前，将针对最速下降法与梯度下降法之间差异性做一些说明。

关于条件数的介绍优点喧宾夺主~本节主要目的不是描述梯度下降法的缺陷，而是描述最速下降法与梯度下降法之间的差异性。

回顾：

条件数

在梯度下降法在强凸函数的收敛性证明中介绍了梯度下降法在$m$-强凸函数上的收敛性定理：

条件：

• 目标函数$f(\cdot )$向下有界，在其定义域内可微；并且$f(\cdot )$是$m$-强凸函数；
• 关于$f(\cdot )$的梯度函数$\nabla f(\cdot )$满足$\mathcal{L}$-利普希兹连续；
• 梯度下降法在迭代过程中，其步长${\alpha }_k$存在明确的约束范围：$\begin{array}{r}{\alpha }_k\in \left(0,\frac{2}{\mathcal{L}+m}\right)\end{array}$；

结论：
数值解序列 { x k } k = 0 ∞ \{x_k\}_{k=0}^{\infty} {xk​}k=0∞​以$\mathcal{Q}$-线性收敛的收敛速度收敛于最优数值解$x^{\ast }$。

在证明过程中，实现了线性收敛的定义式的证明：
$$\begin{array}{rl}\frac{\Vert x_{k+1}-x^{\ast }\Vert }{\Vert x_k-x^{\ast }\Vert }& =\frac{\Vert x_k-\alpha \cdot \nabla f(x_k)-x^{\ast }\Vert }{\Vert x_k-x^{\ast }\Vert }\\ & \le \sqrt{1-\alpha \cdot \frac{2\mathcal{L}m}{\mathcal{L}+m}}\in (0,1)\end{array}$$
如果目标函数$f(\cdot )$满足二阶连续可微的条件下，并且其梯度函数$\nabla f(\cdot )$满足$\mathcal{L}$-利普希兹连续，那么$f(\cdot )$对应的$\text{Hessian Matrix}\Rightarrow {\nabla }^{2}f(\cdot )$必然存在并且有：

• 下面的推导过程详见梯度下降法在强凸函数的收敛性分析。
• 其中$\mathcal{I}$表示单位矩阵。
  $$m\cdot \mathcal{I}\preccurlyeq {\nabla }^{2}f(\cdot )\preccurlyeq \mathcal{L}\cdot \mathcal{I}$$

对正定矩阵${\nabla }^{2}f(\cdot )$进行分解，可得到$n$个正特征值： { λ i } i = 1 n \{\lambda_i\}_{i=1}^n {λi​}i=1n​；
其中$\mathcal{Q}$是正交矩阵。
$${\nabla }^{2}f(\cdot )=\mathcal{Q}\Lambda {\mathcal{Q}}^{-1}=\mathcal{Q}\left(\begin{array}{cccc}{\lambda }_1& & & \\ & {\lambda }_2& & \\ & & \ddots & \\ & & & {\lambda }_n\end{array}\right){\mathcal{Q}}^{-1}$$
这些特征值必然满足：
0 < m ≤ λ m i n ≤ λ m a x ≤ L { λ m i n = min ⁡ { λ i } i = 1 n λ m a x = max ⁡ { λ j } j = 1 n 0 < m \leq \lambda_{min} \leq \lambda_{max} \leq \mathcal L \quad \begin{cases} \lambda_{min} = \min \{\lambda_i\}_{i=1}^n \\ \lambda_{max} = \max \{\lambda_j\}_{j=1}^n \end{cases} 0<m≤λmin​≤λmax​≤L{λmin​=min{λi​}i=1n​λmax​=max{λj​}j=1n​​
在上述条件下，取一种特殊情况：
关于$\begin{array}{r}\alpha =\frac{1}{\mathcal{L}}=\frac{2}{\mathcal{L}+\mathcal{L}}\in \left(0,\frac{2}{\mathcal{L}+m}\right)\end{array}$恒成立,目的是将条件数与收敛速度关联起来。
$${\lambda }_{max}=\mathcal{L};{\lambda }_{min}=m;\alpha =\frac{1}{\mathcal{L}}$$
将上述情况代入原式，那么线性收敛定义式可简化为：
$$\begin{array}{rl}\frac{\Vert x_k-\alpha \cdot \nabla f(x_k)-x^{\ast }\Vert }{\Vert x_k-x^{\ast }\Vert }& \le \sqrt{1-\frac{1}{\mathcal{L}}\cdot \frac{2\mathcal{L}m}{\mathcal{L}+m}}\\ & =\sqrt{\frac{{\lambda }_{max}-{\lambda }_{min}}{{\lambda }_{max}+{\lambda }_{min}}}\\ & =\sqrt{\frac{1-\frac{1}{\mathcal{K}[{\nabla }^{2}f(\cdot )]}}{1+\frac{1}{\mathcal{K}[{\nabla }^{2}f(\cdot )]}}}\end{array}$$
其中$\begin{array}{r}\mathcal{K}[{\nabla }^{2}f(\cdot )]=\frac{{\lambda }_{max}}{{\lambda }_{min}}\end{array}$被称作$\text{Hessian Matrix}\Rightarrow {\nabla }^{2}f(\cdot )$的条件数$(\text{Condition Number})$，可以发现：

• 条件数可看作是目标函数$f(\cdot )$自身的性质，因为它仅与${\nabla }^{2}f(\cdot )$的最大、最小特征值相关。
• 条件数与收敛速度之间的关系：当$\mathcal{K}[{\nabla }^{2}f(\cdot )]$趋近于$\infty$时，有：
  $$\underset{\mathcal{K}[{\nabla }^{2}f(\cdot )]\Rightarrow \infty }{\lim }\frac{\Vert x_k-\alpha \cdot \nabla f(x_k)-x^{\ast }\Vert }{\Vert x_k-x^{\ast }\Vert }\le \underset{\mathcal{K}[{\nabla }^{2}f(\cdot )]\Rightarrow \infty }{\lim }\sqrt{\frac{1-\frac{1}{\mathcal{K}[{\nabla }^{2}f(\cdot )]}}{1+\frac{1}{\mathcal{K}[{\nabla }^{2}f(\cdot )]}}}=\sqrt{\frac{1-0}{1+0}}=1$$
  在取等时，收敛速度将从线性收敛退化至次线性收敛。

也就是说：

• 使用梯度下降法时，在特定条件的情况下，其收敛速度与目标函数$f(\cdot )$自身性质——条件数存在关联关系；
• 条件数越大，收敛速度越慢；该现象被称作病态问题。

范数

范数通常被用来度量向量空间中，向量的长度或大小。我们通常使用特征空间中的点与特征空间原点之间的明可夫斯基距离来描述向量的范数：
$${\mathcal{D}}_{mk}(x,\mathcal{O})={\left[\sum _{k=1}^n(x_k{)}^m\right]}^{\frac{1}{m}}$$
其中$m$表示阶数，上式也称作$m$-阶范数。例如$m=2$对应的二阶范数(也称欧式范数)：
$$\begin{array}{rl}\Vert x{\Vert }_2& ={\left[\sum _{k=1}^n(x_k{)}^2\right]}^{\frac{1}{2}}\\ & =\sqrt{x_1^2+x_2^2+\cdots +x_n^2}\end{array}$$

范数不仅描述了向量的大小；反过来，如果固定范数的阶数和大小，它可以描述满足阶数与大小条件的集合。以二维特征空间为例，在范数大小为$1$的前提下，不同阶数对应的集合形状表示如下：

很明显，当阶数$p<1$是，其对应集合是一个非凸集合；相反，对应集合是一个凸集合。

相关描述

在笔记线搜索方法——方向角度的结尾提到：在当前迭代步骤中，负梯度方向作为下降方向，对应目标函数的下降效果最明显，因而被称作最速下降方向，从而称最速下降法为梯度下降法。但如果详细追究，它们之间依然存在一些区别。

关于梯度下降法

梯度下降法直观地认为：负梯度方向$-\nabla f(\cdot )$是目标函数$f(\cdot )$的值下降最快的方向。对应迭代过程表示如下：
$$x_{k+1}=x_k+\eta \cdot \Delta x_k\Delta x_k=-\nabla f(x_k)$$

因而每次迭代过程中将决策变量$x_k$沿着负梯度方向移动，从而使目标函数值逐渐收敛。思路虽然简单，但由于下降方向$\Rightarrow -\nabla f(\cdot )$被确定，导致梯度下降法的收敛速度非常大的依赖于目标函数$f(\cdot )$自身$\text{Hessian Matrix}$的条件数。
解释:$\text{Hessian Matrix}$并没有直接参与梯度下降法的迭代过程，只是下降方向被确定为$-\nabla f(\cdot )$时，作为$f(\cdot )$自身性质的条件数就已经对梯度下降法的收敛速度进行约束了。

最速下降法

根据上面链接笔记中的描述：负梯度方向只是下降方向的一种，而下降方向${\mathcal{P}}_k$的判定逻辑是：满足目标函数$f(x_{k+1})=f(x_k+{\alpha }_k{\mathcal{P}}_k)$的一阶泰勒展开式与$f(x_k)$之间存在严格的单调性：
其中$\mathcal{O}(\Vert {\alpha }_k{\mathcal{P}}_k\Vert )$表示关于${\alpha }_k{\mathcal{P}}_k$的二阶无穷小。
$$\begin{array}{rl}f(x_{k+1})& =f(x_k+{\alpha }_k{\mathcal{P}}_k)\\ & =f(x_k)+\frac{1}{1!}{\alpha }_k\cdot ({\mathcal{P}}_k{)}^T\nabla f(x_k)+\mathcal{O}(\Vert {\alpha }_k{\mathcal{P}}_k\Vert )\\ & \approx f(x_k)+{\alpha }_k\cdot ({\mathcal{P}}_k{)}^T\nabla f(x_k)\\ \text{Monotonicity: }& \\ f(x_{k+1})-f(x_k)& \approx {\alpha }_k\cdot ({\mathcal{P}}_k{)}^T\nabla f(x_k)<0\\ & \Rightarrow ({\mathcal{P}}_k{)}^T\nabla f(x_k)<0({\alpha }_k>0)\end{array}$$
从方向导数的角度考虑，将第$k$次迭代过程的更新方向记作变量$\mathcal{P}$，从而将最速下降方向${\mathcal{P}}_k$描述为：选择合适的更新方向$\mathcal{P}$，使得$f(x_{k+1})$或者$f(x_{k+1})-f(x_k)$关于$\mathcal{P}$方向的方向导数最小：

• 由于$f(x_k)$是已知项，因而其关于$\mathcal{P}$的方向导数为$0$。但$f(x_{k+1})$与$f(x_{k+1})-f(x_k)$描述的意义不相同，这里使用$f(x_{k+1})-f(x_k)$进行描述。
• 关于该方向导数的描述，见《深度学习(花书)》P55.
  $$\{\begin{array}{l}f(x_{k+1})-f(x_k)={\varphi }_k(\mathcal{P})={\alpha }_k\cdot {\mathcal{P}}^T\nabla f(x_k)\\ \\ {\mathcal{P}}_k=\begin{array}{r}\underset{\mathcal{P}}{\mathrm{argmin}}\frac{\partial {\varphi }_k(\mathcal{P})}{\partial {\alpha }_k}=\underset{\mathcal{P}}{\mathrm{argmin}}{\mathcal{P}}^T\nabla f(x_k)\end{array}\end{array}$$

单位范数的描述

如果对上述最速下降方向进行标准化，即标准化最速下降方向$(\text{Normalized Steepest Descent})$：在单位范数$(\text{Unit Norm})$步长内能够使目标函数下降最多的方向。记作：
需要注意的是，这里的单位范数步长描述的并不是${\alpha }_k$(因为它是标量),而是对$\mathcal{P}$的约束。由于这里仅观察$\mathcal{P}$的变化情况，从而令${\alpha }_k=1$。
$${\mathcal{P}}_{nsd}=\underset{\mathcal{P}}{\mathrm{argmin}}\{[\nabla f(x_k){]}^T\mathcal{P}\mid \Vert \mathcal{P}\Vert \le 1\}$$
对应非标准化的最速下降方向${\mathcal{P}}_{sd}$可表示为：
其中$\Vert \cdot {\Vert }_{\ast }$表示对偶范数;其对应展开式中$\sup$表示上确界。
$$\begin{array}{rl}{\mathcal{P}}_{sd}& =\Vert \nabla f(x_k){\Vert }_{\ast }{\mathcal{P}}_{nsd}\\ & =\sup \left\{[\nabla f(x_k){]}^T{\mathcal{P}}_{nsd}\mid \Vert {\mathcal{P}}_{nsd}\Vert \le 1\right\}\end{array}$$

可以看出：最速下降方向受到单位范数步长的限制。重点在于：不同类型的单位范数步长，其对应的限制范围也存在差异。例如$p=1,2,4$时对应小于单位范数的描述范围对比如下：
其中橙色线描述的单位圆也被称作欧式范数。

再如：矩阵$2$-范数$\Vert z{\Vert }_{\mathcal{Q}}$：对应小于单位范数描述范围表示如下：
关于矩阵2范数$\Vert z{\Vert }_{\mathcal{Q}}=(z^T\mathcal{Q}z{)}^{1/2}$的描述范围与$\mathcal{Q}$的性质相关。下图中的橙色线表示对角矩阵$\mathcal{Q}=\left(\begin{array}{c}10\\ 02\end{array}\right)$的情况;蓝色线则表示正定矩阵$\mathcal{Q}=\left(\begin{array}{c}11\\ 12\end{array}\right)$的情况。

梯度下降法VS最速下降法

梯度下降法等价于最速下降法的情况

如果上述关于${\mathcal{P}}_{nsd}=\underset{\mathcal{V}}{\mathrm{argmin}}\{[\nabla f(x_k){]}^T\mathcal{P}\mid \Vert \mathcal{P}\Vert \le 1\}$的描述中，单位范数步长$||\mathcal{P}||$是欧式范数，那么此时的最速下降法与梯度下降法等价。因为在欧式范数$\Vert \mathcal{P}\Vert \le 1$的描述范围内，某位置$x_k$的标准最速下降方向${\mathcal{P}}_{nsd}$与该位置对应的负梯度方向$-\nabla f(x_k)$相同。举一个例子：

• 假设目标函数$f(x)=x^T\mathcal{Q}x;x\in {\mathbb{R}}^2$是标准型，并且$\mathcal{Q}=\mathcal{I}$(单位矩阵)。该函数的等值线以及欧式范数的描述范围表示如下：
  此时，无论是欧式范数描述范围还是等值线，都是标准圆的格式，因而使得$[\nabla f(x_k){]}^T\mathcal{P}$达到最小的方向就是负梯度方向。
  

• 其中红色虚线表示$f(x)$的等值线；蓝色圆以及内部的灰色阴影表示欧式范数描述范围。在迭代过程中某时刻黄色点$x_k$，此时该点处的梯度方向$\nabla f(x_k)$与负梯度方向$-\nabla f(x_k)$见上图。

• 从最速下降法的角度观察，为了让$x_k$更快地达到最优值点(特征空间原点处所在位置)：

  • 通过计算$[\nabla f(x_k){]}^T\mathcal{P}=\Vert \nabla f(x_k)\Vert \cdot \Vert \mathcal{P}\Vert \cdot \cos \theta$，在向量大小$\Vert \mathcal{P}\Vert$与夹角$\theta$两者的共同作用下，找到最优更新方向(灰色阴影内的绿色箭头)。
    \quad

  至此，找到一个红色点，坐标空间原点指向红色点的向量就是${\mathcal{P}}_{nsd}$。从图像中可以看出：负梯度方向$-\nabla f(x_k)$与${\mathcal{P}}_{nsd}$所指方向完全相同。
  由于欧式范数的原因，${\mathcal{P}}_{nsd}$与$-\nabla f(x_k)$大小、方向均完全相同。

很明显，此时的这种目标函数格式，可以满足：全局范围内，梯度下降方向等价于最速下降方向。

欧式范数约束产生的更新方向可能不是最优方向

那么在其他目标函数中，欧式范数会产生什么样的现象$?$
假设目标函数$f(x)=x^T\mathcal{Q}x;x\in {\mathbb{R}}^2$，其中$\mathcal{Q}$是正定矩阵且$\mathcal{Q}=\left(\begin{array}{c}11\\ 12\end{array}\right)$。假设这里依然使用欧式范数，对应等值线与欧式范数描述范围表示如下：
区别于上图，此时的等值线是椭圆,并且对应正交基与坐标轴不平行。

与上面的配置相同，此时的最速下降法与梯度下降法依然是等价的。绿色箭头表示负梯度方向$-\nabla f(x_k)$或${\mathcal{P}}_{nsd}$。这里发现一个新现象：更新方向$-\nabla f(x)$或${\mathcal{P}}_{nsd}$并没有指向最优方向，也就是说：这里的更新方向并不是最优方向；真正指向最优方向的是红色箭头。

梯度下降法与最速下降法不等价的情况

换一种角度：假设这里没有使用欧式范数，而是使用${\mathcal{L}}_1$范数，也可以得到一些其他效果：

其中绿色箭头描述的是梯度下降法产生的更新方向；红色箭头则描述的是最速下降法的更新方向。很明显：红色箭头描述的位置相比于绿色箭头更接近最优解。此时两者不等价。

范数的选取与收敛速度的关系

范数的选取对于收敛速度产生较大的影响。当目标函数$f(\cdot )$二阶连续可微的情况下，使用矩阵$2$-范数，它的收敛速度会显著提高。在关于目标函数$f(x)$优化问题的迭代过程中，在$x_k$点处如果使用其对应$\text{Hessian Matrix}\Rightarrow {\nabla }^{2}f(x_k)$定义的矩阵$2$-范数，该位置对应的实际更新方向${\mathcal{P}}_{sd}$可表示为：
$${\mathcal{P}}_{sd}=-[{\nabla }^{2}f(x_k){]}^{-1}\nabla f(x_k)$$

这就是经典牛顿法描述的更新方向。
这里不再展开，只是为了描述选取合适的关于更新方向的范数约束，可以提高迭代的收敛速度。

$\text{Reference}$：
笔记 || 梯度法与最速下降法的本质区别