这个答案只会考虑渐近结果，即我们是否在无限次迭代后卡住。我们还将只考虑零噪声的经典梯度下降。GD 的嘈杂变体（例如 SGD）总是有一个非零概率随机远离均衡几个连续步骤，因此它们永远不会真正渐近卡住。虽然经典 GD 的渐近收敛肯定与 SGD 的性能/收敛速度有关，但我认为 SGD 的优化大大超出了原始问题的范围。

我们将考虑陷入不稳定平衡的概率，即鞍点或最大值。我们将通过具有零梯度和非正定的Hessian 矩阵来定义不稳定的平衡。

卡在不稳定的平衡点本身实际上是不可能的。很容易看出 2D 中的点或线的面积为零，因此除非对起点进行微调，否则降落在其上的概率为零。

为了完成对经典GD的分析，还有待观察是否可以构建一个不稳定的平衡，其吸引盆具有与域相同维度的非零面积/超体积，这将使从随机初始着陆的概率点非零。考虑一个具有以下梯度的奇怪鞍点

虽然符号函数可能有点不切实际，但如果我们用 sigmoid 替换它，同样的论点仍然成立。如果我们考虑这个梯度的图（箭头被归一化，因为在渐近分析中我们只关心方向，而不关心大小）

我们发现它的吸引盆（黄色）具有非零面积。有了这种特殊的安排，经典的 GD 有可能并且很可能永远被卡住

一旦触及导数为零的点，旧的梯度下降将终止。如果导数为零，那么也将终止于鞍。但是在日常梯度下降（随机）中，很难或几乎不可能以最大值或鞍点终止，因为这些点不是具有稳定平衡的点，因为函数的 Hessian 矩阵不是肯定的正数。

考虑到最坏情况的初始化，梯度下降确实可以收敛到鞍点（Nesterov 2013，第 1.2.3 节）。

随机初始化可以防止收敛到鞍点

当梯度下降随机初始化时（给定某些假设），情况就不同了。李等人。（2016）证明：

如果$f: \mathbb{R}^d \to \mathbb{R}$是两次连续可微的并且满足严格的鞍性质，然后具有随机初始化和足够小的恒定步长的梯度下降几乎肯定会收敛到局部最小值。

“足够小”的步长意味着小于梯度的 Lipschitz 常数的倒数，他们说这在实践中是标准的。“严格鞍属性”意味着所有临界点（梯度为零）要么是局部最小值，要么是严格鞍（即 Hessian 矩阵至少有一个严格的负特征值）。这个属性并不普遍适用，但他们声称它适用于许多实际感兴趣的目标函数。

证明通过将梯度下降视为一个动态系统来进行。每个临界点都有一个周围的吸引力盆地。如果梯度下降进入这个盆地，那么它将收敛到相应的临界点。鉴于上述假设，鞍点周围的吸引力盆地具有零度量。这意味着，通过随机初始化，在这样的盆地中着陆的概率为零（因此收敛到鞍点）。

逃离鞍点可能需要指数时间

上述结果涉及渐近收敛。它说带有随机初始化的梯度下降最终会收敛到局部最小值，但它不能保证收敛需要多长时间。不幸的是，杜等人。（2017）表明梯度下降可能需要指数时间来逃避鞍点，即使是随机初始化和非病态目标函数。也就是说，存在“自然”目标函数，其中所需的步数与要逃逸的鞍点数呈指数关系。尽管梯度下降最终会在这些情况下收敛，但它可能需要很长的时间。请注意，此结果描述了最坏的情况；这并不意味着所有人的指数时间目标函数。

加速收敛

在存在鞍点的情况下，有多种方法可以加快收敛速度​​（参见 Du et al. 2017 中的参考资料）。一种方法涉及巧妙的初始化方案，但这是特定于问题的。另一种策略利用 Hessian 中的曲率信息，产生多项式时间收敛到局部最小值（这不再是梯度下降）。这需要访问 Hessian（或 Hessian 向量积的计算），并且可能无法扩展到非常大的问题。

如果增加随机扰动，纯基于梯度的方法可以在多项式时间内避开鞍点。直观地说，这是可行的，因为鞍点是不稳定的不动点；如果优化算法被随机推开，它很有可能会移动到其他地方。可以通过显式添加噪声来实现随机扰动。或者，标准随机梯度下降 (SGD) 可能会提供类似的效果，前提是梯度中的噪声在所有方向上都足够大（Ge 等人 2015；然而 Du 等人推测 SGD 通常需要指数时间）。

参考

Du, SS, Jin, C., Lee, JD, Jordan, MI, Singh, A., & Poczos, B. (2017)。梯度下降可能需要指数时间来逃避鞍点。在神经信息处理系统的进展中（第 1067-1077 页）。

Ge, R., Huang, F., Jin, C., & Yuan, Y.（2015 年 6 月）。脱离鞍点——张量分解的在线随机梯度。在学习理论会议上（第 797-842 页）。

Lee, JD, Simchowitz, M., Jordan, MI 和 Recht, B.（2016 年 6 月）。梯度下降只收敛到极小值。在学习理论会议上（第 1246-1257 页）。

内斯特罗夫，Y.（2013 年）。凸优化入门讲座：基础课程（第 87 卷）。施普林格科学与商业媒体。