$\textbf{平时我看起来很坚强，}$
$\textbf{可是遇到你，我会变成另一个模样。}$
$\textbf{我不想考虑太多，}$
$\textbf{因为追随内心，你已经走进我的心墙。}$
$\textbf{我想让你知道，}$
$\textbf{我从未想过放手，}$
$\textbf{只愿陪你到永远。}$
$\qquad\qquad\quad\textbf{——畅宝宝的傻逼哥哥}$

如果一个算法满足这样的性质：任意的初始点$\textbf{x}_0\in X$都会产生一个收敛的点序列$\{\textbf{x}_k\}_{k=0}^\infty$，那么称该算法是全局收敛的。实际上，如果某些条件不满足，甚至非常有效的算法都会失效。例如算法可能产生不收敛的序列或者收敛的点不是所求的解，存在一些导致算法失败的因素，但是如果我们很清楚的了解他们，那么我们就能采取某些避免失败的措施，所以全局收敛成为理论学者与实践者共同的兴趣。

大部分全局收敛理论处理的是保证全局收敛的环境与条件，其中一个重要的理论如下：

$\textbf{定理1：}$令A表示X上的算法并假设初始点$\textbf{x}_0$将产生一个无穷序列$\{\textbf{x}_k\}_{k=0}^{\infty}$，其中

$$\textbf{x}_{k+1}\in A(\textbf{x}_k)$$

如果该算法的解集S与下降函数$D(\textbf{x}_k)$存在，使得

• 所有点$\textbf{x}_k$包含在X的紧子集中
• $D(\textbf{x}_k)$满足下降函数的定义且
• A的映射对S外的所有点都封闭

那么任何收敛序列$\{\textbf{x}_k\}_{k=0}^{\infty}$的极限都是解。

$\textbf{证明：}$这个定理的证明分两部分。对a部分，我们假设$\hat{\textbf{x}}$是任何序列$\{\textbf{x}_k\}_{k=0}^{\infty}$子序列$\{\textbf{x}_k\}_{k\in I}$的极限，其中I是整数的一个集合，并且说明$D(\textbf{x}_k)$对无限序列$\{\textbf{x}_k\}_{k=0}^{\infty}$收敛。对b部分，我们说明$\hat{\textbf{x}}$是集合S的解。

证明的第二部分非常依赖于魏尔斯特拉斯定理，如果W是紧集，那么序列$\{\textbf{x}_k\}_{k=0}^{\infty}$的极限点在W中，其中$\textbf{x}_k\in W$。如果集合W是闭的，那么它也就紧集。如果W边界上的所有点都属于W，那么W是闭集。如果W能被一个有限半径的超球包围，那么W是有界集。魏尔斯特拉斯定理的一个结论是$\{\textbf{x}_k\}_{k=0}^{\infty}$的任何子序列$\{\textbf{x}_k\}_{k\in I}$的极限位于集合$\bar{W}=\{\textbf{x}_k:k\in I\}$中，因为$\bar{W}$是W的子集，所以它也是紧集。

(a)因为$D(\textbf{x}_k)$在X上是连续的且$\hat{\textbf{x}}$是序列$\{\textbf{x}_k\}_{k\in I}$的极限，所以存在正数与整数K使得当$k\geq K$时

$$D(\textbf{x}_k)-D(\hat{\textbf{x}})<\varepsilon$$

其中$k\in I$，因此$D(\textbf{x}_k)$对子序列$\{\textbf{x}_k\}_{k\in I}$收敛。然而我们还必须证明$D(\textbf{x}_k)$对无限序列$\{\textbf{x}_k\}_{k=0}^{\infty}$收敛。

对于任意$k\geq K$，我们有

$$D(\textbf{x}_k)-D(\hat{\textbf{x}})=[D(\textbf{x}_k)-D(\textbf{x}_K)]+[D(\textbf{x}_K)-D(\hat{\textbf{x}})]$$

如果$k=K$，那么

$$D(\textbf{x}_K)-D(\hat{\textbf{x}})<\varepsilon$$

如果$k\geq K$，那么$D(\textbf{x}_k)\leq D(\textbf{x}_K)$，因此

$$D(\textbf{x}_k)-D(\textbf{x}_K)\leq 0$$

由此可得对任意$k\geq K$

$$D(\textbf{x}_k)-D(\hat{\textbf{x}})<\varepsilon$$

因此

$$\lim_{k\to\infty} D(\textbf{x}_k)=D(\hat{\textbf{x}})$$

即当$\textbf{x}_k\to\hat{\textbf{x}}$时$D(\textbf{x}_k)$相对于无限序列收敛。

(b)假设$\hat{\textbf{x}}$不在解集中，因为子序列$\{\textbf{x}_{k+1}\}_{k\in I}$的元素属于属于紧集，根据魏尔斯特拉斯定理可知存在紧子集$\{\textbf{x}_{k+1}:k\in\bar{I}\subset I\}$使得$\textbf{x}_{k+1}$收敛到极限$\bar{\textbf{x}}$。根据部分(a)，我们说明了

$$\lim_{k\to\infty}D(\textbf{x}_{k+1})=D(\bar{\textbf{x}})$$

因此

$$D(\bar{\textbf{x}})=D(\hat{\textbf{x}})$$

另一方面

$$\begin{align*} \textbf{x}_k\to\hat{\textbf{x}}\quad &for\ k\in\bar{I}\\ \textbf{x}_{k+1}\to\bar{\textbf{x}}\quad &for\ \textbf{x}_{k+1}\in A(\textbf{x}) \end{align*}$$

根据假设$\hat{\textbf{x}}\notin S$，并且A对S外的点是闭的，我们有

$$\bar{\textbf{x}}\in A(\hat{\textbf{x}})$$

因此

$$D(\bar{\textbf{x}})<D(\hat{\textbf{x}})$$

得出矛盾，因为$\{\textbf{x}_k\}_{k=0}^{\infty}$的任何收敛子序列的极限是解。

对于简单的情况，上面的定理说明，如果

• 算法生成的点在有限的$E^n$空间中
• 可以找到满足要求的下降函数
• 算法在解邻域的外边是封闭的

那么算法是全局收敛的。进一步，我们可以在有限次迭代下得到近似解，因为$\{\textbf{x}_k\}_{k=0}^{\infty}$的任何有限子序列的极限都是解。

定理1的推论同样非常重要：

$\textbf{推论1：}$如果定理1的条件成立，解集S由一个点$\hat{\textbf{x}}$组成，那么序列$\{\textbf{x}_k\}_{k=0}^{\infty}$收敛到$\hat{\textbf{x}}$。

$\textbf{证明：}$如果我们假设有一个子序列$\{\textbf{x}_k\}_{k\in I}$不收敛到$\hat{\textbf{x}}$，那么对于所有的$k\in I,\varepsilon>0$，

$$\Vert\textbf{x}_k-\hat{\textbf{x}}\Vert>\varepsilon$$

集合$\{\textbf{x}_k\in I^{'}\subset I\}$是紧集，$\{\textbf{x}_k\}$

牛顿迭代法收敛性的一点讨论

今天在使用牛顿迭代法求方程的数值解时，发现其一会儿收敛，一会儿不收敛，于是认证研究了下牛顿迭代法的收敛条件。
牛顿迭代法的收敛性分为局部收敛性与全局收敛性。
**局部收敛性：**若α是f(x)=0的一个单根, f(α)=0,f’(α)≠0,ϕ’(α)=0, ϕ’’(α)=f’’(α)/f’(α), 则在根α附近Newton
法是局部收敛的, 并且是二阶收敛的。这个附近指的是充分接近。要多接近呢？似乎没有进一步的证明。
这就决定了牛顿迭代法的初值选取非常重要，只有在解的附近选初值才具有局部收敛性。可是证明去找解的附近呢？一种方法是先用二分法找一个大概的解，再用牛顿法求解。
然而，对于某些函数，初值离解很远也能收敛，这就要谈到全局收敛性了。
全局收敛性：
设f(x)在有根区间[a, b]上二阶导数存在，且满足
(1) f(a)f(b)<0;
(2) f’(x)≠0, x∈[a, b];
(3) f’’(x)不变号, x∈[a, b];
(4)初值x0 ∈[a, b]且使f’’(x0) *f(x0)>0;
则Newton迭代法收敛于f(x)=0在[a, b]内的惟一根。
其中，条件（2）和（3）要求函数在区间内为凸或凹函数，条件（4）又规定了初值接近解的方向，算是比较苛刻的条件。以f(x)=lnx为例，若选择初值x0为4，则第一次迭代后的值x1为-1.505，超过了定义域，就不收敛了。

可如果初值选择0.5，则是收敛的。

分类目录：《机器学习中的数学》总目录
相关文章：
· 病态
· 局部极小值
· 高原、鞍点和其他平坦区域
· 梯度消失和梯度爆炸
· 非精确梯度
· 局部和全局结构间的弱对应

---

迄今为止，我们讨论的许多问题都是关于损失函数在单个点的性质——若$J(\theta )$是当前点$\theta$的病态条件，或者$\theta$在悬崖中，或者$\theta$是一个下降方向不明显的鞍点，那么会很难更新当前步。

如果该方向在局部改进很大，但并没有指向代价低得多的遥远区域，那么我们有可能在单点处克服以上所有困难，但仍然表现不佳。Goodfellow等人认为大部分训练的运行时间取决于到达解决方案的轨迹长度。如下图所示，学习轨迹将花费大量的时间探寻一个围绕山形结构的宽弧。

大多数优化研究的难点集中于训练是否找到了全局最小点、局部极小点或是鞍点，但在实践中神经网络不会到达任何一种临界点。下图表明神经网络通常不会到达梯度很小的区域。甚至，这些临界点不一定存在。例如，损失函数$-\log p(y|x;\theta )$可以没有全局最小点，而是当随着训练模型逐渐稳定后，渐近地收敛于某个值。对于具有离散的$y$和Softmax分布$p(y|x)$的分类器而言，若模型能够正确分类训练集上的每个样本，则负对数似然可以无限趋近但不会等于零。同样地，实值模型$p(y|x)=N(y;f(\theta ,{\beta }^{-1}))$的负对数似然会趋向于负无穷——如果$f(\theta )$能够正确预测所有训练集中的目标$y$，学习算法会无限制地增加$\beta$。上图给出了一个失败的例子，即使没有局部极小值和鞍点，该例还是不能从局部优化中找到一个良好的代价函数值。

未来的研究需要进一步探索影响学习轨迹长度和更好地表征训练过程的结果。许多现有研究方法在求解具有困难全局结构的问题时，旨在寻求良好的初始点，而不是开发非局部范围更新的算法。

梯度下降和基本上所有的可以有效训练神经网络的学习算法，都是基于局部较小更新。之前的小节主要集中于为何这些局部范围更新的正确方向难以计算。我们也许能计算目标函数的一些性质，如近似的有偏梯度或正确方向估计的方差。在这些情况下，难以确定局部下降能否定义通向有效解的足够短的路径，但我们并不能真的遵循局部下降的路径。目标函数可能有诸如病态条件或不连续梯度的问题，使得梯度为目标函数提供较好近似的区间非常小。在这些情况下，步长为$ϵ$的局部下降可能定义了到达解的合理的短路经，但是我们只能计算步长为$\delta <<ϵ$的局部下降方向。在这些情况下，局部下降或许能定义通向解的路径，但是该路径包含很多次更新，因此遵循该路径会带来很高的计算代价。有时，比如说当目标函数有一个宽而平的区域，或是我们试图寻求精确的临界点（通常来说后一种情况只发生于显式求解临界点的方法，如牛顿法）时，局部信息不能为我们提供任何指导。在这些情况下，局部下降完全无法定义通向解的路径。在其他情况下，局部移动可能太过贪心，朝着下坡方向移动，却和所有可行解南辕北辙，或者是用舍近求远的方法来求解问题。

不管哪个问题最重要，如果存在一个区域，我们遵循局部下降便能合理地直接到达某个解，并且我们能够在该良好区域上初始化学习，那么这些问题都可以避免。最终的观点还是建议在传统优化算法上研究怎样选择更佳的初始化点，以此来实现目标更切实可行。

一些理论结果表明，我们为神经网络设计的任何优化算法都有性能限制。通常这些结果不影响神经网络在实践中的应用。

一些理论结果仅适用于神经网络的单元输出离散值的情况。然而，大多数神经网络单元输出光滑的连续值，使得局部搜索求解优化可行。一些理论结果表明，存在某类问题是不可解的，但很难判断一个特定问题是否属于该类。其他结果表明，寻找给定规模的网络的一个可行解是很困难的，但在实际情况中，我们通过设置更多参数，使用更大的网络，能轻松找到可接受的解。此外，在神经网络训练中，我们通常不关注某个函数的精确极小点，而只关注将其值下降到足够小以获得一个良好的泛化误差。对优化算法是否能完成此目标进行理论分析是非常困难的。因此，研究优化算法更现实的性能上界仍然是学术界的一个重要目标。