分析梯度下降的轨迹，更好地理解深度学习中的优化问题

2019 年 1 月 3 日 极市平台

极市平台是专业的视觉算法开发和分发平台，加入极市专业CV交流群，与6000+来自腾讯，华为，百度，北大，清华，中科院等名企名校视觉开发者互动交流！更有机会与李开复老师等大牛群内互动！

同时提供每月大咖直播分享、真实项目需求对接、干货资讯汇总，行业技术交流。点击文末“阅读原文”立刻申请入群~

来源：机器学习研究会订阅号

摘要：神经网络的优化本质上是一个非凸问题，而简单的基于梯度的算法在实践中似乎总是能够解决这类问题。这种现象是深度学习的核心支柱之一，而目前有许多理论科学家家正试图解开这个谜：为什么基于梯度的方法能够在深度学习的优化中行之有效。

一篇来自 offconvex.org 博客的文章对最近一些试图解决这个问题的工作进行了综述，并且在最后讨论了作者本人与 Sanjeev Arora，Noah Golowich 以及 Wei Hu 等人一起撰写的新论文（https://arxiv.org/pdf/1810.02281.pdf）。在这篇论文中，他们针对深度线性神经网络中的梯度下降问题，提出了一种能够保证以线性速率收敛到全局最小值的方法。关于深度学习应用的论文多如牛毛，而关于基础工作原理的文章弥足珍贵。雷锋网 AI 科技评论全文编译如下。

函数图像曲面方法及其局限性

许多关于深度学习优化的论文都隐含着这样一种假设，即通过建立损失函数图像的曲面（landscape）的几何特性（特别是在临界点，也就是梯度开始消失的点），可以严谨地理解这种优化方法。例如，通过与凝聚态物理中的球形自旋玻璃模型进行类比，Choromanska 等人在 2015 年提出了一个现已在深度学习领域广为人知的观点：

函数曲面猜想（Landscape Conjecture）：

在神经网络优化问题中，次优临界点的 Hessian（二阶导矩阵）的特征值很可能存在负数。换而言之，几乎没有糟糕的局部最小值（让梯度下降算法误认为局部最小值是全局最小值的点），而且几乎所有的鞍点都是严格的。

该猜想的对于各种包括浅层（2 层）模型在内的简单问题的损失函数图像的曲面的强形式已经得到了证明，这样的问题包括矩阵感知（https://papers.nips.cc/paper/6271-global-optimality-of-local-search-for-low-rank-matrix-recovery.pdf）、矩阵补全（https://papers.nips.cc/paper/6048-matrix-completion-has-no-spurious-local-minimum.pdf）、正交张量分解（http://proceedings.mlr.press/v40/Ge15.pdf ）、相位反演（https://arxiv.org/pdf/1602.06664.pdf ）以及带二次激活的神经网络（http://proceedings.mlr.press/v80/du18a/du18a.pdf ）等。目前已经有一些工作针对当函数曲面猜想成立时如何实现梯度下降收敛到全局最小值进行了一些研究。例如，Rong Ge（http://www.offconvex.org/2016/03/22/saddlepoints/ ）、Ben Recht（http://www.offconvex.org/2016/03/24/saddles-again/ ）、Chi Jin 和 Michael Jordan（http://www.offconvex.org/2017/07/19/saddle-efficiency/ ）等人的博客中有一些在这类工作方面非常棒的介绍文章。他们介绍了梯度下降可以如何通过逃离所有严格的鞍点来达到二阶局部最小值（Hessian 为正半定的临界点），以及当将我们对算法添加扰动时这个过程将如何起作用。请注意，在函数曲面猜想下，即当没有糟糕的局部最小值、也没有非严格鞍点时，二阶局部最小值也就是全局最小值。

然而，出于很多原因，函数曲面方法（和函数曲面猜想）显然不能像这样被应用到深度（三层或更多层）的网络上。首先，深度网络通常会引入非严格鞍点(例如，在所有权重都为零的点，详情请参阅 Kawaguchi 等人在2016 发表的论文「Deep Learning without Poor Local Minima」：https://papers.nips.cc/paper/6112-deep-learning-without-poor-local-minima.pdf )。其次，函数曲面方法的观点很大程度上忽视了算法层面上的因素，而在实践中算法层面的因素对深度网络的收敛有很大的影响——比如初始化方法的类型(http://proceedings.mlr.press/v28/sutskever13.html)或批量归一化(http://proceedings.mlr.press/v37/ioffe15.pdf).最后，正如我在之前的文章(http://www.offconvex.org/2018/03/02/acceleration-overparameterization/)中谈到的，基于 Sanjeev Arora和 Elad Hazan(http://proceedings.mlr.press/v80/arora18a/arora18a.pdf )的工作，为经典线性模型添加（冗余）线性层有时可以加速基于梯度的优化过程，这样做尽管会为之前的凸优化问题引入一定的非凸性，但是不会增强模型的表现能力。任何只依赖于临界点属性的函数曲面分析都难以解释这样的现象，因为通过这样的方法，没有什么比优化一个具有全局最小值的临界点的凸目标函数更简单的了。

另一种可能的解决方案？

函数曲面方法在分析深度学习中的优化问题时的局限性说明它可能忽略了太多重要的细节。也许，与其思考「函数曲面方法是否是一种优雅的方法？」不如把问题转向「由特定的初始化方法得到的特定优化器的轨迹有怎样的行为？」

尽管基于轨迹的方法似乎比函数曲面分析更加复杂，但是这种方法已经取得了显著的进展。最近的一些论文(如 Brutzkus and Globerson 2017（http://proceedings.mlr.press/v70/brutzkus17a/brutzkus17a.pdf )；Li and Yuan 2017(https://papers.nips.cc/paper/6662-convergence-analysis-of-two-layer-neural-networks-with-relu-activation.pdf)、Zhong et al. 2017(http://proceedings.mlr.press/v70/zhong17a/zhong17a.pdf)；Tian 2017(http://proceedings.mlr.press/v70/tian17a/tian17a.pdf)；Brutzkus et al. 2018(https://openreview.net/pdf?id=rJ33wwxRb)；Li et al. 2018(http://proceedings.mlr.press/v75/li18a/li18a.pdf)；Du et al. 2018(https://arxiv.org/pdf/1806.00900.pdf)；Liao et al. 2018(http://romaincouillet.hebfree.org/docs/conf/nips_GDD.pdf))已经采用了这种策略，成功地分析了不同类型的浅层模型。此外，基于轨迹的分析也正开始涉足函数曲面方法之外的领域，他们已经针对线性神经网络的情况，成功地实现了在任意深度下使用梯度下降方法收敛到全局最小值。

针对深度线性神经网络的基于轨迹的分析

线性神经网络是带有（或不带有）线性激活函数的全连接神经网络。具体而言，一个输入维度为d0、输出维度为dN、隐层维度为 d1,d2,...,dN-1，深度为 N 的线性网络是一个从 Rd_0 到 Rd_N的线性映射，它被参数化为

其中

可以被看作第j层的权值矩阵。尽管这样的表示方法看起来没有什么特别，但线性神经网络优化过程的复杂度却让人有些惊讶，它们会导致具有多个最小值和鞍点的非凸训练问题。用于线性神经网络的基于梯度的算法被人们认为是一种深度学习中的优化问题理论上的替代品，近一段时间，它们在线性神经网络上的应用受到了极大的关注。

据我所知，Saxe et al.2014(https://arxiv.org/pdf/1312.6120.pdf)的工作首次对深度（三层或更多层）的线性网络进行了基于轨迹的分析，在白化后的数据上处理最小化 L2 损失的梯度流（学习率极小的梯度下降）。尽管这个分析有很重要的贡献，但却并未正式实现收敛到全局最小值，也没有考虑计算复杂度方面的因素（收敛所需的迭代次数）。近期研究 Bartlett et al. 2018（http://proceedings.mlr.press/v80/bartlett18a.html)的研究在解决这些问题的工作上取得了进展，通过将基于轨迹的分析用于线性残差网络的特定环境的梯度下降，即在所有层中统一宽度（d0=d1=d2=...=dN）及初始化方式（对于任意的 j，有 Wj=I）的线性网络。考虑到不同的数据-标签分布（他们将其归纳为「targets」），Bartlett 等人展示了可证明的梯度下降以线性速率收敛到全局最小值的情况——损失函数值在经过O(log1/ε)次迭代后与最优值的差小于ε（大于 0）。

在本文作者与 Sanjeev Arora、Noah Golowich 以及 Wei Hu 合作撰写的一篇新论文（https://arxiv.org/pdf/1810.02281.pdf )中，我们在发挥基于轨迹的方法的功效方面又向前迈进了一步。具体而言，我们分析了任意不包含「瓶颈层」的线性神经网络梯度下降的轨迹，瓶颈层的隐藏维度不小于输入和输出维度之间的最小值（对于任意的 j，有 dj≥min{d0,dN}）；我们还证明了以线性速率到全局最小值的收敛性。我们指出了初始化方法需要满足下面两个条件：（1）近似平衡度：对于任意的 j，有 WTj+1Wj+1≈WjWjT；（2）缺失边界：初始损失小于任意秩缺亏缺解的损失。我们证明这两个条件都是必要条件，不满足其中任意一个都可能导致轨迹不收敛。在线性残差网络的特例中，初始化时的近似平衡度很容易满足，而且对于通过以零为中心的微小随机扰动进行初始化的常见设定也同样成立。后者也会导致出现具有正概率的缺失边界。对于 dN=1 的情况（即标量回归），我们提供了一个能同时满足这两个条件的随机初始化方案，因此能在恒定概率下以线性速率收敛到全局最小值。

我们的分析的关键在于观察「如果权重被初始化到了近似平衡的状态，它们是否会在梯度下降的整个迭代中一直这样保持」。换句话说，优化方法所采取的轨迹遵循下面的特性：

也就是说，在整个时间轴上，所有的层（近似地）都有相同的奇异值集合，每一层的左奇异向量（近似地）与下一层的右奇异向量相同。我们说明了这种规律性意味着梯度下降的稳定地运行下去，从而证明，即使在损失函数图像整体上来说十分复杂时（包括许多非严格鞍点），它可能在优化器所采取的特定轨迹周围表现得尤为良好。

结语

通过函数图像方法解决深度学习中优化问题，即分析与训练使用的算法无关的目标函数的几何性质，从概念上来说十分吸引人。但是这一策略存在固有的局限性，主要是因为它要求整个目标函数都要很优雅，这似乎是一个过于严格的要求。替代函数图像的一种方法是考虑优化器及其初始化方法，并且仅仅沿着所得到的轨迹关注其函数图像。这种替代方法正得到越来越多的关注。函数图像分析目前仅限于浅层（两层）模型，而基于轨迹的方法最近已经可以处理任意深度的模型，证明了梯度下降能以线性速率收敛到全局最小值。但是，由于基于轨迹的分析方法仅仅在线性神经网络上取得了成功，仍有还有很多工作有待完成。在我看来，基于轨迹的方法也将成为我们正式理解深度非线性网络的基于梯度的优化方法的关键。

*推荐文章*

每月大咖直播分享、真实项目需求对接、干货资讯汇总，行业技术交流。点击左下角“阅读原文”立刻申请入群~