今年三月，机器学习领域泰斗级学者 Michael I. Jordan 带领的一个跨多所大学和研究院的团队发表了一篇论文《How to Escape Saddle Points Efficiently》，提出了最基本的算法——梯度下降的一个简单变种，并证明该算法虽形式简单，却足以极其高效地避开鞍点。该研究成果推进了对非凸优化的理解，并可以直接被应用在包含深度学习在内的许多机器学习领域。近日，Off the Convex Path 博客和伯克利人工智能研究所（BAIR）的博客都发表了对该研究的解读文章。机器之心对其进行了编译介绍。
论文地址：https://arxiv.org/abs/1703.00887
非凸优化中一个核心问题是如何避开鞍点。尽管近来的研究已经表明梯度下降（GD）通常可以在迭代了极其多步后最终避开鞍点（参阅 Rong Ge 的博客 http://www.offconvex.org/2016/03/22/saddlepoints/和 Ben Recht 的博客 http://www.offconvex.org/2016/03/24/saddles-again/），但仍然还有一个厄待解决的关键问题：效率。GD 能快速避开鞍点吗，还是会在鞍点附近显著减速？避开鞍点的速率又会随着参数个数（维度）的变化而怎样变化？在这篇文章中，我们介绍了与 Rong Ge、Praneeth Netrapalli 和 Sham Kakade 共同完成的一项研究；这项研究为该效率问题提供了第一个可证明的正面回答。研究相当令人惊讶地表明：仅仅使用适当扰动就足以使GD非常高效地避开鞍点；实际上，从收敛速率对维度依赖上来看，几乎就像是鞍点不存在一样。
扰动梯度下降
在经典梯度下降领域，给定一个函数
，我们的目标是通过在负梯度的方向上移动来找到该函数的最小化：
。其中 xt 是需优化的变量在第t步的值，η是步长。当优化函数是凸函数的情况下，GD已经有了非常好的理论解释；但当优化函数非凸时，已有的研究要少得多。我们仅知道在非凸优化中，GD 可以快速收敛到驻点（∇f(x)=0 的点），这些驻点可能是局部最小点，但也可能是毫无用处的局部最大点或鞍点。
显然，如果 GD 是从一个驻点开始的，那么它就根本不会离开那里，即使那可能是一个局部最大值点；因此为了使GD能避开次优的驻点（例如鞍点），我们必须对 GD 稍微作修改，加入一定程度的随机性。目前的文献已经研究过两种加入随机性的简单方法：
- 间歇的扰动：Ge、Huang、Jin 和 Yuan 2015 年的论文《Escaping From Saddle Points ---
Online Stochastic Gradient for Tensor Decomposition》考虑了
在GD中偶尔加入随机扰动的算法，并且第一次为 GD 避开鞍点提供了多项式时间保证。（参阅上述 Rong Ge 的博客）
- 随机初始化：Lee et
al. 2016 年的论文《Gradient Descent Converges to
Minimizers》表明仅需随机初始化，就可以确保 GD 能渐进地避开鞍点。（参阅上述 Ben Recht 的博客）
渐进性的，甚至多项式时的结果一般来说都很重要，但它们却不能很好地解释为什么很多基于梯度的算法在实际的非凸问题上效果非常好。而且它们也无法保证当用户观察到一段相对平坦的学习曲线时，究竟是在鞍点附近还是已经收敛到局部最小值。最后，它们更无法保证 GD 在非凸优化中能像在凸优化中那样快速解决高维问题。
对于避开鞍点，一种合理方法是使用二阶（基于 Hessian 的）算法。尽管这些算法的在每步更新中计算成本比 GD（远远）更高，而且实现起来也更加复杂，但Hessian确实能直接提供关于鞍点的几何信息，从而在较少的步数内快速避开鞍点。因此，在学界中已经有相当一部分工作给出了基于 Hessian 的算法的较好理论解释，并且也得到了正面的结论。
GD 也可以快速避开鞍点吗？还是说 Hessian 对快速避开鞍点是必需的？
如果仅限于考虑上文提及的“随机初始化”策略，对于这种策略第一个问题的答案是否定的。事实上，这种方法可以被证明一般来说效率很低，在最坏的案例中避开鞍点甚至需要指数级别的大量时间。（见后文「加入扰动的必要性」）
但如果我们考虑“间歇的扰动”策略，我们却能得到一个相当不同而且正面的结果，这或多或少有点让人惊讶。为了陈述这个结果，让我们先澄清一下我们要分析的算法：
其中扰动 ξt 是从一个以 0 为中心，半径适当小的球上均匀采样的；而且当梯度适当小时，这些扰动会被加入到迭代中。这些特定的超参数选择是为了方便分析，我们相信均匀的噪声并不是必需的，只在梯度很小时才加入噪声也不是必要的。
严格鞍点和二阶驻点
后文中讨论的“鞍点”同时指代了一般定义中的鞍点，和局部最大点。这些点是在至少一个方向上为局部最大值的驻点。鞍点和局部最小值可以根据 Hessian 的最小特征值分类：
。
更进一步，我们将最后一类鞍点称为严格鞍点（strict saddle
points），他们满足
。
尽管非严格鞍点在谷底可能是平坦的，但严格鞍点要求至少有一个方向的曲率是严格为负的。这样一个方向的存在让基于梯度的算法有了避开这个鞍点的可能。一般而言，区分局部最小值和非严格鞍点是 NP-hard 的，因此，我们以及之前的研究者关注的都是避开严格鞍点。
在形式上，我们做了两个关于光滑度的标准假设，如下：
经典理论研究收敛到一阶驻点 ∇f(x)=0 的速度，是通过研究找到
ϵ-一阶驻点 （|∇f(x)|≤ϵ）所需的步数。与此类似，我们研究避开严格鞍点的速度，也就是收敛到二阶驻点
的速度，通过研究找到它的ϵ- 弱化版本所需的步数：
在这个定义中，ρ 是前面引入的 Hessian Lipschitz 常数。这种定义方式源于Nesterov 和 Polyak 2016 年的论文《Cubic regularization of Newton method and its global performance》。
应用
在实际应用中，一大类非凸问题都可以被证明具有以下性质：所有的鞍点都是严格鞍点。这类问题包括，且不仅限于主成分分析、典型相关分析、正交张量分解、相位恢复、字典学习、矩阵感知（matrix sensing）、矩阵补全和其它非凸低秩问题。
此外，在所有上述非凸问题中，也可以证明：所有局部最小值都是全局最小值。因此，在这些情况下，任何可以寻找 ε-二阶驻点的通用有效的算法都可以直接有效地找到全局最小值，从而快速解决这些非凸问题。
只需极小额外开销即可避开鞍点
对于经典理论研究的一阶驻点，我们知道 GD 在理论上有非常好的性质：
在这个定理中，x0 是初始点，f⋆ 是全局最小值的函数值。该定理说对于任意梯度-Lipschitz 函数，GD 都可以在
步之内找到一个驻点，且所需步数对维度 d没有显式的依赖。这在文献中被称为「维度无关的优化（dimension-free
optimization）」；当然，每步中进行梯度计算的时间是 O(d)，因此 GD 的整体运行时间会为O(d)的阶。对于深度学习等现代高维非凸问题而言，O(d)这样的线性运算时间是GD非常重要的优势（相比于二阶算法而言
）。
对应地，我们现在同样希望能快速收敛到二阶驻点。对于这个问题，我们能期望得到的最好结果是什么样的呢？我们是否还能实现：
- 维度无关的迭代次数
收敛率- 对 ℓ 和 (f(x0)−f⋆) 的依赖与Nesterov 1998 中的结果完全相同。
相当让人惊讶的是，对于这三个问题，我们给出的答案都是肯定的（额外开销只有一些很小的对数因子）。
这里 O~(⋅) 仅隐藏了对数因子；实际上，我们的结果中的维度依赖只有
。因此，该定理证明了在一个附加的 Hessian-Lipschitz 条件下，一种有扰动的 GD 变种能快速收敛到二阶驻点，且所需的时间与 GD 收敛到一阶驻点所需的时间几乎一样。在这个意义上，我们断言 PGD 可以几乎无需额外开销就能避开严格鞍点。
接下来，我们讨论这样强的结果为什么能成立的一些直观原因。
为什么 polylog(d) 次迭代就够了？
本文中对于严格鞍点假设意味着在最糟糕的情况下，在 d 维度中我们只有一个方向可以避开鞍点。直观来看，要搜索下降方向应该需要至少 poly(d) 次迭代，那为什么我们仅用 polylog(d) 就足够了呢？
考虑一个简单例子，其中我们假设函数在鞍点附近是二次的。也就是说，让目标函数为
，其鞍点在 0 处，并且Hessian H=diag(−1,1,⋯,1)是个常量。在这个例子中，仅有第一个方向是避开的方向（具有负特征值 -1）。
可以直接得出这个例子中梯度下降所给出的通项公式：
假设我们从 0 处的鞍点开始，先加入一个扰动 x0 是从以 0 为中心，1 为半径的球 B0(1) 上均匀采样的。函数值的减少情况可以表示为：
设步长为 1/2，令 λi 表示 Hessian H 中的第 i 个本征值，令
表示初始点 x0 的第 i 个方向的分量。我们有
，因此：
简单的概率计算表明在 B0(1) 上均匀采样将有很高的概率得到第一个方向的至少一个
Ω(1/d) 分量。也就是说：
。代入上式中的
α1，我们看到要让函数值减少一定常量，最多只需要 O(logd) 步。
用于一般 Hessian 的薄饼形状的滞留区（stuck region）
在上述二次函数的例子中，我们可以总结得到，只有当扰动 x0不幸落到集合
中时，我们才需要很长时间来避开鞍点。我们称这个集合为滞留区（stuck region）；在这个案例中，这是一个碟状的平坦区域。一般来说，当 Hessian 不再是常量时，这个滞留区将会变成扭曲的薄饼形状，如下面左图中的绿色结构。一般来说，这个区域不会有解析表达式。
分析鞍点周围的GD行为的早期尝试往往用一个扁平的集合来近似这个滞留区。这使得步长需要选得非常小，并导致了非常大的总运行时间复杂度。我们理论中给出的快速收敛率取决于一个关键的想法——尽管我们不知道滞留区的具体形状，但我们知道它非常薄。
为了表征该薄饼的「薄度」，我们研究了在一个避开方向上距离为
的假想的成对扰动后所得的初始点 w,u。我们断言如果我们从 w 和 u 开始运行 GD，得到的轨迹中至少有一个可以非常快地避开鞍点。这表明滞留区的厚度最多为
，所以随机扰动落在滞留区的几率非常小。
加入扰动的必要性
我们已经讨论了两种修改标准梯度下降算法的可能方法，第一种是通过添加间歇的扰动，另一种是通过随机初始化。尽管后者表现出了渐进的收敛性，但它一般无法得到高效的收敛。在最近与Simon Du、Jason Lee、Barnabas Poczos和Aarti Singh合作共同完成的研究《Gradient Descent Can Take Exponential Time to Escape Saddle Points》中（http://arxiv.org/abs/1705.10412），我们表明即使使用了相当自然的随机初始化方案和非病态（pathological）函数，仅使用随机初始化的 GD 也可能在鞍点附近显著变慢，避开鞍点需要的总时间也可能按指数级别增长。PGD 的行为则非常不同，它一般可以在多项式时间内避开鞍点。
为了严格证明这个结果，我们考虑了一大类的常用随机初始化方法，其中包括在超立方体（hypercube）上的高斯和均匀分布，然后我们构建了一个满足假设 1 和 2 的光滑的目标函数。这个函数使得即使使用随机初始化，GD 和 PGD 在达到局部最小值之前都有很高的可能性必须依次通过d 个严格鞍点附近。所有的严格鞍点都仅有一个避开方向。（d=2 的情况参见左图）
当 GD 在一系列鞍点附近前进时，它可能会与后面的鞍点越来越近，因此避开鞍点就需要越来越长的时间。实际上，避开第i个鞍点所需的时间会按 e^i 的速度增长。而 PGD 总是能在少量步数内避开任何鞍点，无论是第几个鞍点。我们通过实验确认了这种现象，比如，上面右图中 d=10 的情况。
结论
在这篇文章中，我们展示了一种梯度下降的扰动形式可以快速收敛到二阶驻点，且速度和标准梯度下降收敛到一阶驻点的速度一样快。这表明 Hessian 信息对有效避开鞍点而言并不是必需的，这也帮助解释了 GD 和 SGD 等基本梯度下降算法在非凸环境中效果良好的原因。这种新的快速收敛结果可以直接应用于矩阵感知/补全等非凸问题，并直接给出了很快的全局收敛速率。
当然，在一般的非凸优化上，还仍然有很多悬而未决的问题。举几个例子：加入动量（momentum）可以提升到二阶驻点的收敛速度吗？什么样的局部最小值容易处理，以及有没有我们可以用于局部最小值的结构性假设使GD可以有效地避开局部最小值？我们正在非凸优化上取得缓慢但稳健的进展，我们希望某天，非凸优化能从「黑箱」，充斥着无法解释得「小技巧」的现状，最终变成一门「科学」。
原文链接：http://bair.berkeley.edu/blog/2017/08/31/saddle-efficiency/
