现代应用研究的很多方面都依赖于一种称为梯度下降的关键算法。这是一个通常用于寻找特定数学函数的最大值或最小值的过程——这个过程被称为优化函数。它可用于计算任何事情，从最有利可图的产品制造方式到为工人分配轮班的最佳方式。
然而，尽管其应用广泛，研究人员从未完全理解算法在哪些情况下最困难。现在，新的研究工作解释了这一点，确定梯度下降从本质上解决了一个根本困难的计算问题。新的研究结果限制了研究人员在特定应用中期望的性能类型。
「它有一种最坏情况值得去了解，」牛津大学的 Paul Goldberg 说，他与利物浦大学（University of Liverpool）的 John Fearnley 和 Rahul Savani 以及牛津大学的 Alexandros Hollender 共同撰写了这项工作。
研究成果《The complexity of gradient descent: CLS = PPAD ∩ PLS 》获得 6 月份的 2021 年度 ACM 计算理论研讨会 (STOC) 最佳论文奖。
你可以将一个函数想象成一个景观，其中土地的海拔等于该特定地点的函数值（「利润」）。梯度下降通过在给定位置寻找最陡峭上升的方向并从它下坡搜索来搜索函数的局部最小值。景观的坡度称为梯度，因此得名梯度下降。
梯度下降是现代应用研究的重要工具，但它在许多常见问题上效果不佳。但在这项研究之前，并没有全面了解究竟是什么以及何时让梯度下降陷入困境以——计算机科学领域一个被称为「计算复杂性理论」有助于回答这个问题。
麻省理工学院的 Costis Daskalakis 说：「梯度下降的很多工作都没有涉及复杂性理论。」
计算复杂性是对解决或验证不同计算问题的解决方案所需的资源（通常是计算时间）的研究。研究人员将问题分为不同的类别，同一类别中的所有问题共享一些基本的计算特征。
举个例子——一个与新论文相关的例子——想象一个城镇，人多于房子，每个人都住在房子里。给你一本电话簿，上面写着镇上每个人的姓名和地址，你需要找到住在同一所房子里的两个人。你知道你可以找到答案，因为人多于房子，但这可能需要一些查找（特别是如果他们没有相同的姓氏）。
这个问题属于一个称为 TFNP 的复杂性类，是「全函数非确定性多项式」（total function nondeterministic polynomial）的缩写。它是所有计算问题的集合，这些问题保证有解决方案，并且可以快速检查其解决方案的正确性。研究人员专注于 TFNP 中两个问题子集的交集。
第一个子集称为 PLS（多项式局部搜索）。这是一系列问题，涉及在特定区域中寻找函数的最小值或最大值。保证这些问题的答案可以通过相对直接的推理找到。
属于 PLS 类别的一个问题是规划一条路线的任务，该路线允许你以最短的旅行距离访问一些固定数量的城市，因为你只能通过切换任意一对连续城市的顺序来更改旅行。计算任何建议路线的长度很容易，并且由于你可以调整行程的方式受到限制，因此很容易看出哪些更改会缩短行程。保证你最终会找到一条无法通过可接受的移动来改进的路线 —— 局部最小值。
第二个子集是 PPAD（有向图上的多项式奇偶校验参数）。这些问题的解决方案来自更复杂的过程，称为 Brouwer 不动点定理。该定理说，对于任何连续函数，都保证有一个点保持不变，也就是不动点。在日常生活中也是如此。如果你搅拌一杯水，该定理保证绝对必须有一个水粒子会回到它开始的地方。
PLS 和 PPAD 类的交集本身形成了一类称为「PLS int PPAD」 的问题。它包含着许多与复杂性研究人员相关的自然问题。然而，直到现在，研究人员都无法找到一个对 PLS int PPAD 来说是完整的自然问题；这意味着它是此类中最难的问题之一。
在这篇论文之前，唯一已知的 PLS int PPAD-complete 问题是一个「相当人为的构造」——这个问题有时被称为「Either-Solution」。该问题将一个来自 PLS 的完整问题和一个来自 PPAD 的完整问题粘合在一起，形成了一个研究人员在这种情况下不太可能遇到的问题。在新论文中，研究人员证明了梯度下降与任一解决方案一样难，使梯度下降本身 PLS int PPAD-complete。
「『计算的本质』是我们作为一个物种应该尝试深入了解其所有形式的东西。我认为这个结果应该足以让我们感到兴奋。」哥伦比亚大学的 Tim Roughgarden 说。
这并不意味着梯度下降会一直挣扎。事实上，对于大多数用途，依然快速和有效。
「关于计算复杂性有一种略带幽默的刻板印象，即我们经常做的是『解决一个在实践中节省了很多时间』的问题，并证明它实际上非常困难。」Goldberg 说。
但结果确实意味着，应用研究人员不应期望，梯度下降能够为某些高精度的问题，提供精确的解决方案。
精度问题会涉及计算复杂性的核心问题——资源需求的评估。在许多复杂问题中，精度和速度之间存在基本联系。如果希望使算法被认为是有效的，则应当想方设法提高解决方案的精度，而不应该选择付出高昂的代价来使用此类解决方案。新的研究结果表明，对于需要非常精确解决方案的应用程序，梯度下降可能不是一种可行的方法。
例如，梯度下降通常以「不需要极端精度」的方式用于机器学习。但是往往机器学习研究人员可能希望将实验的精度继续提高。在这种情况下，新结果意味着他们可能需要将梯度下降算法的运行时间增加四倍。虽然这样并不理想，但也能达成目的。
对于其他应用，如数值分析，研究人员可能需要调整精度。为了实现这样的改进，他们可能只能对梯度下降的运行时间进行平方，这使得计算变得更加复杂与困难。
Daskalakis 说：「『它』]阻止了『他们』可能拍摄的目标。」
他们必须，而且在实践中确实会在某处妥协。他们要么接受不太精确的解决方案，将自己限制在稍微简单的问题上，要么找到一种方法来管理笨拙的运行时。
但这并不是说梯度下降的快速算法不存在。它可能。但结果确实意味着任何这样的算法都会立即暗示存在针对 PLS int PPAD 中所有其他问题的快速算法——比仅仅为梯度下降本身寻找快速算法要高得多。
「许多可能是数学进步的问题都可以解决，」Daskalakis 说。「这就是为什么我们喜欢有一个非常自然的问题，比如梯度下降，它可以捕捉整个交叉点的复杂性。」
