推荐|机器学习笔记之优化算法(十七)梯度下降法在强凸函数的收敛性分析

机器学习笔记之优化算法——梯度下降法在强凸函数的收敛性分析

引言
- 回顾：梯度下降法在强凸函数的收敛性
- 二阶可微——梯度下降法在强凸函数的收敛性推论

引言

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

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

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

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

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

根据 $\mathcal Q$ -线性收敛的定义，关于结论的证明可转化为下述公式成立：

\frac{∣∣ x _{k + 1} - x ^{*} ∣∣}{∣∣ x _{k} - x ^{*} ∣∣} \leq a \in (0, 1) k = 1, 2, 3, \dots

其证明过程见上一节——梯度下降法在强凸函数上的收敛性证明，这里不再赘述。最终我们得证：

\frac{∣∣ x _{k} - α \cdot \nabla f ( x _{k} ) - x ^{*} ∣∣}{∣∣ x _{k} - x ^{*} ∣∣} \leq 1 - α \cdot \frac{2 L m}{L + m}

并有：

\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)$ 二阶可微，则有：
使用拉格朗日中值定理进行表示： $∀x,y∈Rn,\existξ∈(x,y)⇒||∇2f(ξ)||=||∇f(x)−∇f(y)||||x−y||$
$\forall x, y \in R^{n}, \exists ξ \in (x, y) \Rightarrow ∣∣ \nabla^{2} f (ξ) ∣∣ = \frac{∣∣\nabla f ( x ) - \nabla f ( y ) ∣∣}{∣∣ x - y ∣∣}$
$||\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 (λ1λ2⋱λn)$

\mathcal Q^{-1}

\nabla^{2} f (\cdot) = Q Λ Q^{- 1} = Q λ_{1} λ_{2} ⋱ λ_{n} 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(λ1−mλ2−m⋱λn−m) \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)$ ，必然有：
${L⋅I−∇2f(⋅)=Q(L−λ1L−λ2⋱L−λn)Q−1L−λi≥0i=1,2,⋯,mL−λmax≥0⇒λmax≤L$

对上述大小关系进行整理，最终有：
$\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$ -强凸函数的条件。

如果令：

m = λ_{min}; L = λ_{ma x}; α = \frac{1}{L}

，这相当于对

\mathcal L

-利普希兹连续、

m

-强凸函数两个条件进行了更严苛的约束，继续对上述

\mathcal Q

-线性收敛公式：

\frac{∣∣ x _{k} - α \cdot \nabla f ( x _{k} ) - x ^{*} ∣∣}{∣∣ x _{k} - x ^{*} ∣∣} \leq 1 - α \cdot \frac{2 L m}{L + m}

进行化简：

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

\frac{∣∣ x _{k} - α \cdot \nabla f ( x _{k} ) - x ^{*} ∣∣}{∣∣ x _{k} - x ^{*} ∣∣} \leq 1 - α \cdot \frac{2 L m}{L + m} = 1 - \frac{1}{L} \cdot \frac{2 L m}{L + m} = \frac{L - m}{L + m} = \frac{λ _{ma x} - λ _{min}}{λ _{ma x} + λ _{min}}

将根号内分子、分母同时除以

\lambda_{min}

：

其中 $\frac{λ _{ma x}}{λ _{min}}$ 被称作 $\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)]$ 。
$\frac{∣∣ x _{k} - α \cdot \nabla f ( x _{k} ) - x ^{*} ∣∣}{∣∣ x _{k} - x ^{*} ∣∣} \leq \frac{\frac{λ _{ma x}}{λ _{min}} - 1}{\frac{λ _{m a x}}{λ _{min}} + 1} = \frac{K [ \nabla ^{2} f ( \cdot )] - 1}{K [ \nabla ^{2} f ( \cdot )] + 1} = \frac{1 - \frac{1}{K [ \nabla ^{2} f ( \cdot )]}}{1 + \frac{1}{K [ \nabla ^{2} f ( \cdot )]}}$

通过观察可以发现：如果 $\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$
这意味着：

\frac{∣∣ x _{k} - α \cdot \nabla f ( x _{k} ) - x ^{*} ∣∣}{∣∣ x _{k} - x ^{*} ∣∣} \leq 1

，而这意味着此时的收敛速度位于退化边缘。
如果上式取等的话，那么收敛速度会从

\mathcal Q

-线性收敛退化至次线性收敛。
因而通常称条件数

\mathcal K[\nabla^2 f(\cdot)]

过大的现象称作病态问题。

这也体现了梯度下降法的弊端：如果函数 $f(\cdot)$ 二阶可微，其对应 $\nabla^2 f(\cdot)$ 的条件数过大可能会导致梯度下降法收敛速度的退化。
而条件数的大小依赖

\frac{λ _{ma x}}{λ _{min}}

,也就是说：它依赖

\lambda_{max}

与

\lambda_{min}

的差异性的大小。因而这个条件数仅取决于

f(\cdot)

是否二阶可微这条性质上。而这条性质同样是

f(\cdot)

的自身性质。一旦

f(\cdot)

确定且二阶可微，那么其

\nabla^2 f(\cdot)

确定，从而条件数确定。

机器学习笔记之优化算法——梯度下降法在强凸函数的收敛性分析

引言

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

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

评论记录：