机器之心原创
作者：Joshua Chou 编辑：Joni Zhong 译：大魔王
在一篇题为“Escaping from saddle points on Riemannian manifolds”的论文中，华盛顿大学和加州大学伯克利分校的研究人员深入探讨了优化问题的细节，这对于理解机器学习的底层数学非常重要 学习。 重要的。 本文是对论文的解读。
引言 “优化”泛指最大化或最小化一个函数，函数的集合通常代表一系列受约束的备选方案。 我们可以通过比较集合中不同的函数选择来确定哪个函数是“最好的”。 学习是模型迭代学习最小化误差函数或最大化奖励函数的过程。 以分类任务的简单线性回归为例。 误差函数是模型输出和真实数据输出之间的均方误差。 学习过程是求线性函数y = a^Tx b的系数a_i和b_i，以最小化y（模型输出）和y*（真实输出）之间的Error。 例如，学习（即优化）通常是使用梯度下降算法通过反向传播迭代完成的。 在每次迭代中，系数 a_i 和 b_i 是一个选择（在所有可能的 a_i 和 b_i 值的集合中），算法将学习下一组使误差函数最小化的系数。 因此，模型的学习过程归根结底是一个优化问题。 论文“Escaping from saddle points on Riemannian manifolds”深入探讨了优化问题的细节，这对于理解机器学习的底层数学非常重要。 在经典的最小化任务中，基于梯度的优化方法是寻找局部最小值最常用的方法。 “陷入鞍点”问题出现在基于梯度的优化方法中。 优化问题旨在找到能够使目标函数达到局部最小值的停滞点，鞍点就是不能达到局部最小值的停滞点强>。 因此，了解如何识别和避免鞍点至关重要。 本文介绍了一种识别和避免目标函数满足流形约束的鞍点的新方法。 集合 本文考虑了光滑流形 M 上非凸光滑函数的最小化：
其中 M 是 d 维光滑流形，f 是二次可微函数，Hessian 拟合 ρ-Lipschitz。 寻找此类问题的全局最小值具有挑战性，本文使用一阶优化方法来寻找近似的二阶驻点（达到局部最小值）。 当到达停滞点时，作者介绍了一种方法来识别停滞点是鞍点还是局部最小值。 此外，作者提出了一种避免鞍点并尝试将目标函数收敛到局部最小值的方法。 随着越来越多的应用被建模为大规模优化问题，更简单的一阶方法变得越来越重要。 所以论文对非凸问题使用一阶方法，看看效果。 具体来说，作者对黎曼流形上的非凸问题进行了优化。 背景知识在深入研究本文之前，我们需要了解一些基本的数学概念。 理想情况下，本文要求读者对高斯几何有基本的了解，即三维欧氏空间中曲线和曲面的几何。 此外，微分几何的知识也很重要。 但是，我将尝试在本文中解释一些术语的含义。 每个光滑的 d-流形 M 对 R^n 是局部微分同胚的。 M 中的每个点周围都有一个平坦（小）邻域。 因此，它服从 R^n 上的欧几里德度量。 从视觉上看，这意味着 M 中的每个点都有一个零曲率的小邻域和围绕它的欧几里得度量。 接下来，我们需要知道一个可微分流形M在M内部的x点处的切空间TxM。切空间是一个与M同维的向量空间。读者需要理解这个概念：在标准的R^n中， 点 x ∈ R^n 处的切向量 v 可以解释为对围绕 x 局部定义的实值函数的一阶线性可微运算。 这可以推广到流形设置。 现在我们来看黎曼流形。 黎曼流形具有黎曼度量。 黎曼度量为我们提供了每个切线空间上的标量积，可用于测量流形上曲线的角度和长度。 它定义了距离函数并自然地将流形转换为度量空间。 假设读者理解了曲率的概念，我们来看一下黎曼曲率张量和黎曼流形的截面曲率。 我们可以将黎曼曲率张量理解为流形的曲率，这与我们对曲率的直观理解是一致的。 曲率读者可以在标准来源中找到截面曲率的定义，其想法是将曲率分配给平面。 切线空间中平面 p 的一部分的曲率与初始方向为 P 的测地线扫过的表面的高斯曲率成正比。直观地说，这是通过给定平面的二维切片，您需要测量其 二维曲率。 符号 本文重点研究使用黎曼度量 g 的光滑 d 维黎曼流形 (M,g)。 点 x ∈ M 的切空间为 TxM。 邻域定义为：Bx(r) = { v ∈ TxM, ||v|| ≤ r }，即在切线空间 TxM 内以 0 为中心、半径为 r 的球体。 在任意点 x ∈ M，度量 g 自然地导出切空间 上的内积：TxM x TxM → R。黎曼曲率张量表示为 R(x)[u, v]，其中 x ∈ M 和 u, v ∈ TxM。 截面曲率为K(x)[u, v], x ∈ M, u, v ∈ TxM，定义如下：
本文用d(x, y)表示截面之间的距离 两点在 M 之间的距离（根据黎曼度量）。 测地线 γ : R → M 是一条等速曲线，其长度等于 d(x, y)，即测地线是连接 x 和 y 的最短路径。 指数映射 Exp_x(v) 将 v ∈ TxM 映射到 y ∈ M，则存在测地线 γ 使得 γ(0) = x, γ(1) = y, (d/dt)γ(0) = v . 这个概念比较难理解，读者可以按照下面的方法来理解索引映射。 将指数映射视为沿切向量 v 的方向推动点 x 一小段距离。如果我们可以将该点沿测地线 γ 推动 1 个距离单位，那么我们将到达点 y。 另一种理解方式是投影。 假设点p1的坐标为(x_1,y_1,z_1)，z_1=0，即p1在x-y平面上。 将向量p2(x_2, y_2, z_2)与p1相加，其中z_2不等于0，即p3 = p1 p2。 现在，使用投影定理，将 p3 投影回 x-y 平面得到 p4。 根据投影定理，p4和p1之间的距离最短。 测地线是球体或其他曲面或流形上两点之间的最短路径。 指数映射类似于此示例中的投影运算符。 主要算法 对黎曼流形进行优化的主要算法如下：
算法1看起来很吓人，但是作者给出的总结对于理解算法机制很有用。 算法 1 的工作原理如下：
算法 1 依赖于流形的指数映射，适用于指数映射易于计算的情况（许多常见流形的指数映射也易于计算）。 作者直观地展示了它：
图1：鞍点在球面上的函数f。 函数f的定义为：f(x) = (x_1)^2 − (x_2)^2 4(x_3)^2，如图1所示。算法在x_0初始化，这是一个鞍点。 在其切线空间中向 x_0 添加噪声，然后计算将点 x_0 映射回流形上的点 x_1 的指数映射。 该算法然后运行黎曼梯度下降并停止在 x*，这是局部最小值。 主定理背后的概念算法背后的思想很简单，但底层证明更为复杂。 我尝试简要直观地解释结果并提供一些见解。 详细证明及相关文献见原论文。 假设论文做了多个假设，前两个关于 f，最后一个关于 M：
简单来说，Lipschitz 连续性是连续性的定量版本。 给定 x 和 y 之间的距离 d(x,y)，Lipschitz 函数为 f(x) 和 f(y) 之间的距离设置了定量上限。 如果 C 是 f 的 Lipschitz 值，则距离最多为 C×d(x, y)。 假设 1 和 2 是梯度和 Hessian 矩阵的标准 Lipschitz 条件，即常数 β 和 ρ 分别描述梯度和 Hessian 矩阵的“最坏情况”分离。 这些假设主要是为了保证梯度和Hessian是可微的。 类似地，假设 3 为 M 的截面曲率设置了上限。直观上，该假设旨在确保指数映射不会无限增长。 例如，对于一个点x∈M，切空间TxM和围绕x的曲率最大。 TxM 中的点的指数映射 Exp_x (v) 可能会产生一个点 y∈M，y 离 x 很远。 那么该算法就没有用了，因为该算法只想稍微远离鞍点到达另一个点，以避开鞍点而去到另一个静止点。 主要定理 主要定理如下所示。 本质上，该定理确保了目标函数的下降率（收敛到停滞点）。 证明策略是经过一定的迭代次数，当接近鞍点时，函数的值大概率会减小。
上图看起来比较复杂，我们可以从中得到以下信息：
- big O notation和step size rule都有关系 为 β，因此我们可以得出结论，梯度的 Lipschitz 常数 β 越大，算法的收敛时间越长。
- ρ与参数ε直接相关，扰动黎曼梯度下降算法会以1/(2 ε^2)的速度避开鞍点。
- 流形的维数是另一个影响 ε 的参数。 我们可以看到 d 以对数方式影响收敛速度。
论文的证明策略是，经过一定的迭代次数，当接近鞍点时，函数的值很可能会减小。 作者进一步证明，在完成算法的扰动和执行 T 步后，如果迭代次数仍远离鞍点，则函数减小。 结论 本文研究了执行函数 f(x) 最小化的约束优化问题，该函数满足多个流形约束和一些关于 f(x) 的假设。 研究表明，只要函数和流形具有适当的光滑度，扰动黎曼梯度下降算法就可以避免鞍点。
