转载

算法优化之道：避开鞍点

凸函数比较简单——它们通常只有一个局部最小值。非凸函数则更加复杂。在这篇文章中，我们将讨论不同类型的临界点（ critical points），当你在寻找凸路径（ convex path ）的时候可能会遇到。特别是，基于梯度下降的简单启发式学习方法，在很多情形下会致使你在多项式时间内陷入局部最小值（ local minimum ）。

临界点类型

算法优化之道：避开鞍点

为了最小化函数 f : R ⁿ → R ，最流行的方法就是往负梯度方向前进 ∇ f ( x ) （为了简便起见，我们假定谈及的所有函数都是可微的），即：

y = x − η ∇ f ( x ),

其中η表示步长。这就是梯度下降算法（ gradient descent algorithm）。

每当梯度∇f（x）不等于零的时候，只要我们选择一个足够小的步长η，算法就可以保证目标函数向局部最优解前进。当梯度∇f(x)等零向量时，该点称为临界点（ critical point ），此时梯度下降算法就会陷入局部最优解。对于（强）凸函数，它只有一个临界点（ critical point ），也是全局最小值点（ global minimum ）。

然而，对于非凸函数，仅仅考虑梯度等于零向量远远不够。来看一个简单的实例：

y = x ₁ ² − x ₂ ² .

当 x =( 0 , 0 ) 时，梯度为零向量，很明显此点并不是局部最小值点，因为当 x=( 0 , ϵ ) 时函数值更小。在这种情况下， ( 0 , 0 ) 点叫作该函数的鞍点（ saddle point ）。

为了区分这种情况，我们需要考虑二阶导数∇ ² f（x）——一个n × n 的矩阵（通常称作Hessian矩阵），第i,j项等于算法优化之道：避开鞍点。当Hessian矩阵正定时（即对任意的u ≠ 0 ，有 u ^⊤ ∇ ² f（x）u > 0恒成立），对于任何方向向量 u ，通过二阶泰勒展开式，可知 x 必定是一个局部最小值点。同样，当Hessian矩阵负定时，此点是一个局部最大值点；当Hessian矩阵同时具有正负特征值时，此点便是鞍点。

对于许多问题，包括 learning deep nets ，几乎所有的局部最优解都有与全局最优解（global optimum）非常相似的函数值，因此能够找到一个局部最小值就足够好了。然而，寻找一个局部最小值也属于NP-hard问题（参见 Anandkumar ，GE 2006 中的讨论一节）。实践当中，许多流行的优化技术都是基于一阶导的优化算法：它们只观察梯度信息，并没有明确计算Hessian矩阵。这样的算法可能会陷入鞍点之中。

在文章的剩下部分，我们首先会介绍，收敛于鞍点的可能性是很大的，因为大多数自然目标函数都有指数级的鞍点。然后，我们会讨论如何对算法进行优化，让它能够尝试去避开鞍点。

对称与鞍点

许多学习问题都可以被抽象为寻找k个不同的分量（比如特征，中心…）。例如，在聚类问题中，有n个点，我们想要寻找k个簇，使得各个点到离它们最近的簇的距离之和最小。又如在一个两层的神经网络中，我们试图在中间层寻找一个含有k个不同神经元的网络。在我先前的文章中谈到过张量分解（ tensor decomposition ），其本质上也是寻找k个不同的秩为1的分量。

解决此类问题的一种流行方法是设计一个目标函数：设x ₁ ，x ₂ ，…，x _K ∈R ⁿ 表示所求的中心（centers），让目标函数f(x ₁ ,…,x)来衡量函数解的可行性。当向量x ₁ ，x ₂ ，…，x _K 是我们需要的k的分量时，此函数值会达到最小。

这种问题在本质上是非凸的自然原因是 转置对称性 （ permutation symmetry ）。例如，如果我们将第一个和第二个分量的顺序交换，目标函数相当于：f（x ₁ ，x ₂ ，…，x _k ）= f（x ₁ ，x ₂ ，…，x _k ）。

然而，如果我们取平均值，我们需要求解的是算法优化之道：避开鞍点，两者是不等价的！如果原来的解是最优解，这种均值情况很可能不是最优。因此，这种目标函数不是凸函数，因为对于凸函数而言，最优解的均值仍然是最优。

算法优化之道：避开鞍点

所有相似解的排列有指数级的全局最优解。鞍点自然会在连接这些孤立的局部最小值点上出现。下面的图展示了函数y = x ₁ ⁴ −2x ₁ ² + X ₂ ² ：在两个对称的局部最小点（−1,0）和（1,0）之间，点（0,0）是一个鞍点。

算法优化之道：避开鞍点

避开鞍点

为了优化这些存在许多鞍点的非凸函数，优化算法在鞍点处（或者附近）也需要向最优解前进。最简单的方法就是使用二阶泰勒展开式：

算法优化之道：避开鞍点

如果∇f(x)的梯度为零向量，我们仍然希望能够找到一个向量u，使得u ^⊤ ∇ ² f(x)u<0。在这种方式下，如果我们令y = x +ηu，函数值f(Y)就会更小。许多优化算法，诸如 trust region algorithms 和 cubic regularization 使用的就是这种思想，它们可以在多项式时间内避开鞍点。

严格鞍函数

通常寻找局部最小值也属于NP-hard问题，许多算法都可能陷入鞍点之中。那么避开一个鞍点需要多少步呢？这与鞍点的表现良好性密切相关。直观地说，如果存在一个方向u，使得二阶导u ^T ∇ ² f(x)u明显比0小，则此鞍点x表现良好（ well-behaved ）——从几何上来讲，它表示存在一个陡坡方向会使函数值减小。为了量化它，在我与Furong Huang, Chi Jin and Yang Yuan 合作的一篇论文中介绍了严鞍函数的概念（在 Sun et al. 2015 一文中称作“ridable”函数）

对于所有的x，如果同时满足下列条件之一，则函数f(x)是严格鞍函数：

1. 梯度∇f(x)很大。

2. Hessian矩阵∇ ² f(x)具有负的特征值。

3. 点x位于局部极小值附近。

从本质上讲，每个点x的局部区域看起来会与下图之一类似：

算法优化之道：避开鞍点

对于这种函数， trust region算法和 cubic regularization 都可以有效地找到一个局部最小值点。

定理（非正式）：至少存在一种多项式时间算法，它可以找到严格鞍函数的局部最小值点。

什么函数是严格鞍？ Ge et al. 2015 表明张量分解（ tensor decomposition ）问题属于严格鞍。 Sun et al. 2015 观察到诸如完整的 dictionary learning ， phase retrieval 问题也是严格鞍。

一阶方法避开鞍点

Trust region算法非常强大。然而它们需要计算目标函数的二阶导数，这在实践中往往过于费时。如果算法只计算函数梯度，是否仍有可能避开鞍点？

这似乎很困难，因为在鞍点处梯度为零向量，并且没有给我们提供任何信息。然而，关键在于鞍点本身是非常不稳定的（ unstable ）：如果我们把一个球放在鞍点处，然后轻微地抖动，球就可能会掉下去！当然，我们需要让这种直觉在更高维空间形式化，因为简单地寻找下跌方向，需要计算Hessian矩阵的最小特征向量。

为了形式化这种直觉，我们将尝试使用一个带有噪声的梯度下降法（ noisy gradient descent ）

y = x − η ∇ f ( x )+ ϵ .

这里ϵ是均值为0的噪声向量。这种额外的噪声会提供初步的推动，使得球会顺着斜坡滚落。

事实上，计算噪声梯度通常比计算真正的梯度更加省时——这也是随机梯度法（ stochastic gradient ）的核心思想，大量的工作表明，噪声并不会干扰凸优化的收敛。对于非凸优化，人们直观地认为，固有的噪声有助于收敛，因为它有助于当前点远离鞍点（ saddle points ）。这并不是bug，而是一大特色！

算法优化之道：避开鞍点

在此之前，没有良好的迭代上限（upper bound）能够确保避开鞍点并到达局部最小值点（local minimum）。在 Ge et al. 2015 ,我们展示了：

定理（非正式）：噪声梯度下降法能够在多项式时间内找到严格鞍函数的局部最小值点。

多项式高度依赖于维度N和Hessian矩阵的最小特征值，因此不是很实用。对于严格鞍问题，找到最佳收敛率仍是一个悬而未决的问题。

最近 Lee et al. 的论文表明如果初始点是随机选择的，那么即使没有添加噪声，梯度下降也不会收敛到任何严格鞍点。然而他们的结果依赖于动态系统理论（dynamical systems theory）的稳定流形定理(Stable Manifold Theorem) ，其本身并不提供任何步数的上界。

复杂鞍点

通过上文的介绍，我们知道算法可以处理（简单）的鞍点。然而，非凸问题的外形更加复杂，含有退化鞍点（ degenerate saddle points ）——Hessian矩阵是半正定的，有0特征值。这样的退化结构往往展示了一个更为复杂的鞍点（如 monkey saddle （猴鞍），图（a））或一系列连接的鞍点（图（b）（c））。在 Anandkumar, Ge 2016 我们给出了一种算法，可以处理这些退化的鞍点。

算法优化之道：避开鞍点