机器学习笔记之优化算法(十七)梯度下降法在强凸函数的收敛性分析-Toy模板网

这篇具有很好参考价值的文章主要介绍了机器学习笔记之优化算法(十七)梯度下降法在强凸函数的收敛性分析。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

引言

上一节介绍并证明了：梯度下降法在强凸函数上的收敛速度满足 $\mathcal Q$ -线性收敛。
本节将介绍：在更强的条件下：函数 $f(\cdot)$ 在其定义域内二阶可微，梯度下降法在 $f(\cdot)$ 上的收敛速度存在什么样的结论。

回顾：梯度下降法在强凸函数的收敛性

关于梯度下降法在 $m$ -强凸函数上的收敛性定理表示如下：
条件：

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

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

根据 $\mathcal Q$ -线性收敛的定义，关于结论的证明可转化为下述公式成立：
$\begin{aligned}\frac{||x_{k+1} - x^*||}{||x_k - x^*||} \leq a \in (0,1) \quad k = 1,2,3,\cdots\end{aligned}$
其证明过程见上一节——梯度下降法在强凸函数上的收敛性证明，这里不再赘述。最终我们得证：
$\begin{aligned}\frac{||x_k - \alpha \cdot \nabla f(x_k) - x^*||}{||x_k- x^*||} \leq \sqrt{1 - \alpha \cdot \frac{2\mathcal L m}{\mathcal L + m}}\end{aligned}$
并有： $\begin{aligned}\sqrt{1 - \alpha \cdot \frac{2\mathcal L m}{\mathcal L + m}}\end{aligned} \in (0,1)$ 恒成立。

二阶可微——梯度下降法在强凸函数的收敛性推论

如果函数 $f(\cdot)$ 向下有界，并且 $f(\cdot)$ 是 $m$ -强凸函数，在其定义域内二阶可微。在凸函数 $\text{VS}$ 强凸函数中介绍的：根据强凸函数的二阶条件， $f(\cdot)$ 对应的 $\text{Hessian Matrix} \Rightarrow \nabla^2 f(\cdot)$ 存在，并且必然有：
其中 $\mathcal I$ 是单位矩阵。
$\nabla^2 f(\cdot) \succcurlyeq m \cdot \mathcal I$
也就是说： $\nabla^2 f(\cdot) - m \cdot \mathcal I \succcurlyeq 0$ ，即：矩阵 $\nabla^2 f(\cdot) - m \cdot \mathcal I$ 是半正定矩阵。
继续观察条件：如果梯度函数 $\nabla f(\cdot)$ 满足 $\mathcal L$ -利普希兹连续，并且 $f(\cdot)$ 二阶可微，则有：
使用拉格朗日中值定理进行表示： $\begin{aligned}\forall x,y \in \mathbb R^n,\exist \xi \in (x,y) \Rightarrow ||\nabla^2 f(\xi)|| = \frac{||\nabla f(x) - \nabla f(y)||}{||x - y||}\end{aligned}$
$||\nabla^2 f(\cdot)|| \leq \mathcal L$
将范数符号去掉，可表示为：
$-\mathcal L \cdot \mathcal I \preccurlyeq \nabla^2 f(\cdot) \preccurlyeq\mathcal L \cdot \mathcal I$
但又由于 $f(\cdot)$ 是 $m$ -强凸函数的性质，因而 $\nabla^2 f(\cdot)$ 存在更强的下界： $\cdot \mathcal I \geq -\mathcal L \cdot \mathcal I$ ，因而只需认知它的上界即可：
$\nabla^2 f(\cdot) \preccurlyeq\mathcal L \cdot \mathcal I$
也就是说： $\mathcal L \cdot \mathcal I - \nabla^2 f(\cdot) \succcurlyeq 0$ ，即：矩阵 $\mathcal L \cdot \mathcal I - \nabla^2 f(\cdot)$ 是半正定矩阵。
将上述两个结论合并，有：
$\cdot \mathcal I\preccurlyeq \nabla^2 f(\cdot) \preccurlyeq \mathcal L \cdot \mathcal I$

继续观察 $\nabla^2 f(\cdot)$ ，由于 $\nabla^2 f(\cdot) \succcurlyeq m\cdot \mathcal I$ 且 $m > 0$ ，因此 $\nabla^2 f(\cdot)$ 自身不仅是一个实对称矩阵，并且还是一个正定矩阵。因而可以对 $\nabla^2 f(\cdot)$ 进行特征值分解：
其中 $\lambda_1,\lambda_2,\cdots,\lambda_n$ 表示 $\text{Hessian Matrix} :[\nabla^2 f(\cdot)]_{n \times n}$ 的 $n$ 个特征值。而 $n$ 表示特征空间维数，与 $\in \mathbb R^n$ 是同一个 $n$ 。
$\nabla^2 f(\cdot) = \mathcal Q \Lambda \mathcal Q^{-1} = \mathcal Q \begin{pmatrix} \lambda_1 &\quad&\quad&\quad \\ \quad &\lambda_2& \quad&\quad \\ \quad &\quad& \ddots&\quad \\ \quad & \quad& \quad & \lambda_n \end{pmatrix}\mathcal Q^{-1}$
假设对角矩阵 $\Lambda$ 中的特征值按照大到小的顺序排列：
在降维——最大投影方差角度中对特征值的大小关系进行描述过。可以将 $\lambda_1$ 对应的特征向量视作第一主成分,后续以此类推。
$\lambda_{max} = \lambda_1 \geq \lambda_2 \geq \lambda_3 \geq \cdots \geq \lambda_n = \lambda_{min}$

观察矩阵： $\nabla^2 f(\cdot) - m\cdot \mathcal I$ ，将特征值分解结果代入，有：
由于单位矩阵 $\mathcal I = \mathcal Q \mathcal Q^{-1}$ ,因此 $\cdot \mathcal I = \mathcal Q m \mathcal Q^{-1}$
$\nabla^2 f(\cdot) - m\cdot \mathcal I = \mathcal Q \Lambda \mathcal Q^{-1} - \mathcal Q m \mathcal Q^{-1} = \mathcal Q\begin{pmatrix} \lambda_1-m &\quad&\quad&\quad \\ \quad &\lambda_2-m& \quad&\quad \\ \quad &\quad& \ddots&\quad \\ \quad & \quad& \quad & \lambda_n-m \end{pmatrix} \mathcal Q^{-1}$
由于矩阵 $\nabla^2 f(\cdot) - m\cdot \mathcal I$ 是半正定矩阵，因而必然有：
$\lambda_i - m \geq 0 \quad i=1,2,\cdots,n$
也就是说： $\lambda_{min} - m \geq 0 \Rightarrow \lambda_{min} \geq m$
同理，观察矩阵： $\mathcal L \cdot \mathcal I - \nabla^2 f(\cdot)$ ，必然有：
$\begin{cases} \begin{aligned} & \mathcal L \cdot \mathcal I - \nabla^2 f(\cdot) = \mathcal Q\begin{pmatrix} \mathcal L - \lambda_1 &\quad&\quad&\quad \\ \quad &\mathcal L - \lambda_2& \quad&\quad \\ \quad &\quad& \ddots&\quad \\ \quad & \quad& \quad & \mathcal L - \lambda_n \end{pmatrix} \mathcal Q^{-1} \\ & \mathcal L - \lambda_i \geq 0 \quad i=1,2,\cdots,m \\ & \mathcal L - \lambda_{max} \geq 0 \Rightarrow \lambda_{max} \leq \mathcal L \end{aligned} \end{cases}$

对上述大小关系进行整理，最终有：
$\leq \lambda_{min} \leq \lambda_{max} \leq \mathcal L$
回顾上一节——梯度下降法在强凸函数上的收敛性证明过程中，关于辅助函数 $\mathcal G(\cdot)$ 的梯度 $\nabla \mathcal G(\cdot)$ 满足余强制性时，有如下式子成立：
$[\nabla \mathcal G(x) - \nabla \mathcal G(y)]^T(x - y) \geq \frac{1}{\mathcal L - m} ||\nabla \mathcal G(x) - \nabla \mathcal G(y)||^2$
当时我们对 $\mathcal L,m$ 之间的大小关系仅限于 $\mathcal L \geq m$ ，但一旦二阶可微的函数 $f(\cdot)$ 被确定，那么对应的 $\text{Hessian Matrix} \Rightarrow \nabla^2 f(\cdot)$ 以及 $\lambda_{max},\lambda_{min}$ 都是被确定的。也就是说：关于常数 $\mathcal L,m$ 满足： $\leq \lambda_{min} \leq \lambda_{max} \leq \mathcal L$ ，才有该函数 $f(\cdot)$ 满足 $\mathcal L$ -利普希兹连续，以及 $m$ -强凸函数的条件。

如果令： $\begin{aligned}m = \lambda_{min};\mathcal L = \lambda_{max};\alpha = \frac{1}{\mathcal L}\end{aligned}$ ，这相当于对 $\mathcal L$ -利普希兹连续、 $m$ -强凸函数两个条件进行了更严苛的约束，继续对上述 $\mathcal Q$ -线性收敛公式： $\begin{aligned}\frac{||x_k - \alpha \cdot \nabla f(x_k) - x^*||}{||x_k- x^*||} \leq \sqrt{1 - \alpha \cdot \frac{2\mathcal L m}{\mathcal L + m}}\end{aligned}$ 进行化简：

关于步长变量 $\alpha$ 的取值，我们将 $\mathcal L$ -利普希兹连续条件下的最优步长 $\begin{aligned}\frac{1}{\mathcal L}\end{aligned}$ 代入其中。关于最优步长的推导过程详见二次上界引理,这里不再赘述。
$\begin{aligned}0 < \frac{1}{\mathcal L} = \frac{2}{\mathcal L + \mathcal L} \leq \frac{2}{\mathcal L + m} \quad \mathcal L>0;\mathcal L\geq m\end{aligned}$
由于条件中自身存在关于步长的约束: $\begin{aligned}\alpha \in \left(0,\frac{2}{\mathcal L + m}\right)\end{aligned}$ ,需要观察一下 $\begin{aligned}\frac{1}{\mathcal L}\end{aligned}$ 是否位于该范围内见上式~。

$\begin{aligned} \frac{||x_k - \alpha \cdot \nabla f(x_k) - x^*||}{||x_k- x^*||} & \leq \sqrt{1 - \alpha \cdot \frac{2\mathcal L m}{\mathcal L + m}} \\ & = \sqrt{1 - \frac{1}{\mathcal L} \cdot \frac{2 \mathcal L m}{\mathcal L + m}} \\ & = \sqrt{\frac{\mathcal L - m}{\mathcal L + m}} = \sqrt{\frac{\lambda_{max} - \lambda_{min}}{\lambda_{max} + \lambda_{min}}} \end{aligned}$
将根号内分子、分母同时除以 $\lambda_{min}$ ：

其中 $\begin{aligned}\frac{\lambda_{max}}{\lambda_{min}}\end{aligned}$ 被称作 $\text{Hessian Matrix} \Rightarrow \nabla^2 f(\cdot)$ 的条件数 $(\text{Condition Number})$ ，记作 $\mathcal K[\nabla^2 f(\cdot)]$ 。这里并不关注它的性质，仅从推倒的角度观察 $\mathcal K [\nabla^2 f(\cdot)]$ 变化对收敛速度的影响。这里推荐一篇关于条件数的文章，见文章末尾链接。
分子、分母同时除以 $\mathcal K[\nabla^2 f(\cdot)]$ 。
$\begin{aligned}\frac{||x_k - \alpha \cdot \nabla f(x_k) - x^*||}{||x_k- x^*||} & \leq \sqrt{\frac{\frac{\lambda_{max}}{\lambda_{min}} - 1}{\frac{\lambda_{\max}}{\lambda_{min}} + 1}} \\ & = \sqrt{\frac{\mathcal K [\nabla^2 f(\cdot)] - 1}{\mathcal K[\nabla^2 f(\cdot)] + 1}} \\ & = \sqrt{\frac{1 - \frac{1}{\mathcal K [\nabla^2 f(\cdot)]}}{1 + \frac{1}{\mathcal K [\nabla^2 f(\cdot)]}}} \end{aligned}$

通过观察可以发现：如果 $\mathcal K[\nabla^2 f(\cdot)]$ 充分大，有：
$\mathop{\lim}\limits_{\mathcal K[\nabla^2 f(\cdot)] \Rightarrow \infty}\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$
这意味着： $\begin{aligned}\frac{||x_k - \alpha \cdot \nabla f(x_k) - x^*||}{||x_k- x^*||} \leq 1\end{aligned}$ ，而这意味着此时的收敛速度位于退化边缘。
如果上式取等的话，那么收敛速度会从 $\mathcal Q$ -线性收敛退化至次线性收敛。
因而通常称条件数 $\mathcal K[\nabla^2 f(\cdot)]$ 过大的现象称作病态问题。

这也体现了梯度下降法的弊端：如果函数 $f(\cdot)$ 二阶可微，其对应 $\nabla^2 f(\cdot)$ 的条件数过大可能会导致梯度下降法收敛速度的退化。
而条件数的大小依赖 $\begin{aligned}\frac{\lambda_{max}}{\lambda_{min}}\end{aligned}$ ,也就是说：它依赖 $\lambda_{max}$ 与 $\lambda_{min}$ 的差异性的大小。因而这个条件数仅取决于 $f(\cdot)$ 是否二阶可微这条性质上。而这条性质同样是 $f(\cdot)$ 的自身性质。一旦 $f(\cdot)$ 确定且二阶可微，那么其 $\nabla^2 f(\cdot)$ 确定，从而条件数确定。