梯度下降法 数学家澄清了现代应用中最重要的算法的本质

现代应用研究的许多方面都依赖于一种叫做梯度下降的关键算法。这是一个通常用于寻找特定数学函数的最大或最小值的程序——过程被称为优化函数。它可以用来计算任何东西，从制造产品的最优流程到给工人分配班次的最佳方式。

然而，尽管有如此广泛的用途，研究人员从未完全理解该算法在哪些情况是病态的。现在，新的工作解释了这一点，确立了梯度下降法的本质就是解决一个某类困难计算问题，进而找到它最勉为其难的应用场合。

牛津大学的Paul Goldberg说："它有最坏情况，值得了解。"他与利物浦大学的John Fearnley和 Rahul Savani以及牛津大学的Alexandros Hollender是论文的共同作者。他们的工作在6月份年度计算理论研讨会上获得了最佳论文奖。

你可以把一个函数想象成一个地貌景观，土地的海拔等于函数在那个特定地点的价值("利润")。梯度下降法寻找函数的局部最小值，方法是在给定的位置寻找最陡峭的上升方向，并从该方向往下搜索。景观的坡度被称为梯度，因此被称为梯度下降。

梯度下降法是现代应用研究的一个重要工具，但有许多常见的问题，它的效果并不好。但是在这项研究之前，数值计算专家对究竟是什么原因使梯度下降法陷入困境以及何时陷入困境并没有全面的了解。这需要另一个计算科学领域里——计算复杂性理论——的学者来回答。

麻省理工学院的Costis Daskalakis说："梯度下降法的研究，在很多方面，都缺少复杂性理论的加盟。”

计算复杂性是对解决或验证不同计算问题的解决方案所需资源的研究，资源通常是计算时间。研究人员将问题分为不同的类别，同一类别的所有问题都有一些基本的计算特征。

举个与新论文相关的例子——想象一个人比房子多的城镇，每个人都住在一个房子里。给你一本有镇上每个人的名字和地址的电话簿，让你找到住在同一所房子里的两个人。你知道你能找到答案但可能需要花点时间。

这个问题属于一个叫做TFNP的复杂性类别，即 "总函数非确定性多项式" 的简称。它是所有保证有解的计算问题的集合，其解可以快速检查正确性。研究人员专注于TFNP中两个问题子集的交集。

第一个子集被称为PLS(多项式局部搜索)。这是一个问题的集合，涉及在一个特定区域内寻找一个函数的最小值或最大值。这些问题保证有答案，可以通过相对直接的推理找到。

属于PLS类别的一个问题是规划一条路线，使你能以最短的旅行距离访问一些固定数量的城市，因为你只能通过改变旅行中任何一对连续城市的顺序来改变行程。很容易计算出任何建议路线的长度，而且，由于对你调整行程的方式有限制，很容易看出哪些改变会缩短行程。你最终必然能找到一条无法用可接受的举动来进一步改善的路线——一个局部最小值。

第二个问题子集是PPAD(有向图上的多项式奇偶性论证)。这些问题的解决方案是由一个更复杂的过程产生的，这个过程应用所谓的布劳威尔的不动点定理。该定理说，对于任何连续函数，保证有一个点是该函数的值保持不变。这在日常生活中是真实的。如果你搅动一杯水，该定理保证绝对会有一个水分子最终会停留在它最开始在的地方。

PLS和PPAD类的交集本身形成了一类被称为PLS int PPAD的问题。它包含了许多与复杂性研究者相关的自然问题。然而，直到现在，研究人员还无法找到一个对PLS int PPAD来说自然的完全问题——这意味着它是属于这类问题中最难的一个例子。

在这篇论文之前，唯一已知的PLS int PPAD完全问题是一个相当造作的问题——有时被称为 "Either-Solution" 的问题。这个问题将PLS中的一个完全问题和PPAD中的一个完全问题拼接在一起，形成了一个在研究背景之外不太可能遇到的问题。在新的论文中，研究人员证明了梯度下降和Either-Solution一样难，所以 梯度下降法本身就是PLS和PPAD的完全问题。

这并不意味着梯度下降法会一直病态。事实上，对于大多数用途来说，它和以前一样快速和有效。

Goldberg说："关于计算复杂性有一个略带幽默的刻板印象，即我们最终所做的往往在证明一个在实践中很多时候都能解决的问题，实际上是非常困难的。"

但这一结果确实意味着应用研究人员不应该期望梯度下降能够为一些精度很重要的问题提供精确的解。

精度问题涉及到计算复杂性的核心问题--对资源需求的评估。在许多复杂性问题中，精度和速度之间存在着基本的联系。要使一个算法被认为是有效的，你必须能够提高一级的精度，又不需要在时间上付出相应的高代价。这个新结果意味着，对于需要非常精确的解决方案的应用，梯度下降可能不是一个可行的方法。

他们必须，而且在实践中也确实在某处作出妥协。他们要么接受一个不那么精确的解，要么将自己限制在稍微容易的问题上，要么找到一种方法来管理一个不方便的运行时间。

但这并不是说梯度下降的快速算法不存在。它可能存在。但这一结果确实意味着，任何这样的算法将立即意味着PLS和PPAD中所有其他问题的快速算法的存在——这比仅仅找到梯度下降的快速算法本身要重大得多。

"这就是为什么我们喜欢有一个非常自然的问题，如梯度下降法，它是整个交叉学科的复杂性的纲，纲举则目张。"

https://www.quantamagazine.org/computer-scientists-discover-limits-of-major-research-algorithm-20210817/