非凸函数上，随机梯度下降能否收敛？能，但有条件，且比凸函数收敛更难

©作者 | 陈萍、杜伟

来源 | 机器之心

非凸优化问题被认为是非常难求解的，因为可行域集合可能存在无数个局部最优点，通常求解全局最优的算法复杂度是指数级的（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）是一种经典的方法。另一种方法是在开始梯度下降之前建立一个网格并找出全局最小值的大区域。

大家如何看待这个问题呢？感兴趣的小伙伴请在留言区积极发言。

参考链接：https://www.reddit.com/r/MachineLearning/comments/slnvzw/d_can_stochastic_gradient_descent_converge_on/

特别鸣谢

感谢 TCCI 天桥脑科学研究院对于 PaperWeekly 的支持。TCCI 关注大脑探知、大脑功能和大脑健康。

更多阅读

#投 稿 通 道#

 让你的文字被更多人看到 

如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。

总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。 

PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学术热点剖析、科研心得或竞赛经验讲解等。我们的目的只有一个，让知识真正流动起来。

📝 稿件基本要求：

• 文章确系个人原创作品，未曾在公开渠道发表，如为其他平台已发表或待发表的文章，请明确标注 

• 稿件建议以 markdown 格式撰写，文中配图以附件形式发送，要求图片清晰，无版权问题

• PaperWeekly 尊重原作者署名权，并将为每篇被采纳的原创首发稿件，提供业内具有竞争力稿酬，具体依据文章阅读量和文章质量阶梯制结算

📬 投稿通道：

• 投稿邮箱：hr@paperweekly.site 

• 来稿请备注即时联系方式（微信），以便我们在稿件选用的第一时间联系作者

• 您也可以直接添加小编微信（pwbot02）快速投稿，备注：姓名-投稿

△长按添加PaperWeekly小编

🔍

现在，在「知乎」也能找到我们了

进入知乎首页搜索「PaperWeekly」

点击「关注」订阅我们的专栏吧