问题|非凸函数上，随机梯度下降能否收敛？能有条件，比凸函数收敛更难收敛|条件|于非|梯度|ta|非凸函

机器之心报道
编辑：陈萍、杜伟

非凸优化问题被认为是非常难求解的，因为可行域集合可能存在无数个局部最优点，通常求解全局最优的算法复杂度是指数级的（NP 困难）。那么随机梯度下降能否收敛于非凸函数？针对这一问题，众多网友进行了一番讨论。

在机器学习领域，我们经常会听到凸函数和非凸函数，简单来讲，凸函数指的是顺着梯度方向走，函数能得到最优解，大部分传统机器学习问题都是凸的。而非凸指的是顺着梯度方向走能够保证是局部最优，但不能保证是全局最优，深度学习以及小部分传统机器学习问题都是非凸的。
在寻求最优解的过程中，研究者通常采用梯度下降算法。近日， reddit 上的一个热议帖子，帖子内容为「随机梯度下降能否收敛于非凸函数？」

文章图片

原贴内容包括：大量的研究和工作表明梯度下降算法可以收敛于（确定性）凸函数、可微和利普希茨连续函数：
【问题|非凸函数上，随机梯度下降能否收敛？能有条件，比凸函数收敛更难】

文章图片

然而，在非凸函数领域，基于梯度下降算法（例如随机梯度下降）的收敛程度有多大，目前看来研究还不够充分。例如，神经网络中的损失函数几乎是非凸的。非凸函数通常有鞍点（即损失函数的一阶导数为 0 的点），我们可以将这些鞍点视为「陷阱」，鞍点的存在阻止梯度下降到最优点，因为梯度下降在导数为 0 时不能向前移动。

文章图片

两座山中间的鞍点（双纽线的交叉点）
在机器学习、深度学习中使用的优化算法除了常见的梯度下降和随机梯度下降，还包括其他版本，例如 Nesterov 动量、Adam、RMSprop 等几种优化器，这些优化器旨在让梯度远离鞍点。对于这些算法，发帖者很熟悉，但 ta 比较感兴趣的是随机梯度下降算法本身的理论局限性有哪些？
在过去的几周里，发帖人一直在阅读有关这个主题的文章，但是理解其中一些结果所需的数学知识远远超出了 ta 的能力范围。为了弄清这个问题， ta 也查阅了大量的文献，以下是其中 2 篇：
文献 1：Stochastic Gradient Descent for Nonconvex Learning without Bounded Gradient Assumptions

随机梯度下降被大量应用于非凸函数，但研究者对非凸函数的随机梯度下降的理论尚未完全了解（目前仅对凸函数的随机梯度下降有了解）；
现阶段随机梯度下降要求对梯度的一致有界性施加一个假设；
论文作者建立了非凸函数随机梯度下降理论基础，使有界假设可以消除而不影响收敛速度；
论文建立了应用于非凸函数随机梯度下降收敛的充分条件和最优收敛速度。

文献 2 ：Stochastic Gradient Descent on Nonconvex Functions with General Noise Models

尽管随机梯度下降的最新进展值得注意，但这些进展是建立在对正在优化的函数施加了某些限制（例如，凸性、全局利普希茨连续等）的基础之上；
作者证明，对于一般类的非凸函数，随机梯度下降迭代要么发散到无穷大，要么收敛到概率为 1 的静止点；
作者进一步限制并证明，无论迭代是发散还是保持有限 —— 在随机梯度下降的迭代中评估的梯度函数的范数以概率 1 收敛到零，并且符合预期；从而扩大了随机梯度下降可以应用于的函数范围，同时保持对其全局行为的严格保证。

发帖人表示：基于这些文献，我们是否真的能够证明（随机）梯度下降有潜力在非凸函数上显示类似的全局收敛性质，达到之前仅在凸函数上显示收敛程度？
但是我们仍然有理由相信（随机）梯度下降与凸函数相比在非凸函数上收敛更困难。
网友：问题改成「梯度下降在什么条件下会收敛于非凸函数」更好
针对发帖者的这一问题 —— 随机梯度下降能否收敛于非凸函数？网友纷纷从自身经验进行解答。机器之心从中挑选出了几个获赞较多的回复。
首先来看网友 @anonymousTestPoster 的回答。 ta 表示，假设存在一个表现良好的非凸函数，可以参见 Issam Laradji 撰写的《非凸优化》文档。
地址：https://www.cs.ubc.ca/labs/lci/mlrg/slides/non_convex_optimization.pdf
如果存在向下延伸至 Hessian 矩阵的 Lipschitz 连续性限制，则文档 19 页中的 Thm 似乎表明可以不断取得进展以接近顶点。

文章图片

如果想要更复杂的函数，则几乎可以肯定需要的函数是可微的或者利普希茨连续，否则只能选择一些处处连续、无处可微的疯狂函数（crazy function），例如 Weierstrass 函数。
所以，关于「随机梯度下降能否收敛于非凸函数」这一问题， ta 认为在某些条件下「会」，因为很多非凸函数它们可能扰乱 wrt 可微性。在提出反例时，永远不要低估数学家的想象力。
所以， ta 建议发帖者将问题改成「梯度下降在什么条件下会收敛于某类非凸函数」，然后将每类函数作为子问题进行研究，并消除打破传统梯度下降方法的非凸函数反例。

文章图片

接着来看网友 @astone977 指出了原贴内容中存在的一些问题。 ta 表示，当发帖者认为神经网络的误差表面是非凸时，则损失函数也是非凸的。但是， MSE 等损失函数是凸函数。将一个非凸映射（神经网络）应用于一个损失函数的输入，可以创建一个非凸误差表面。
如果我们将 MSE、BCE 等凸函数称为损失函数，那么不应该使用相同的术语来描述一个神经网络的非凸误差表面。这在过去一直是造成混乱的根源，所以 ta 指了出来。

文章图片

最后，网友 @Funktapus 也表示，如果发帖者只是在讨论优化期间避免局部最小值，则这是优化领域一个普遍且非常古老的问题。通常而言，答案是「会」。
我们可以使用随机方法来跳出小的局部最小值。蒙特?卡罗方法（Monte Carlo）是一种经典的方法。另一种方法是在开始梯度下降之前建立一个网格并找出全局最小值的大区域。