这种最常见 AI 技巧之一，意外发现新局限丨计算机理论顶会 STOC 最佳论文
许多现代的应用研究都依赖于一种称为梯度下降法的关键算法。这是一个经常被用来查找特定数学函数最大值或最小值的过程，该过程称为优化函数。它可以用来计算任何东西，譬如获取最大利益的产品生产方式或是为工人分配最佳的轮班次序。
然而，尽管梯度下降法有着广泛的用途，研究人员却从未完全理解该算法在哪些情况下会表现挣扎。现在，新的研究工作解释了这一点，确定梯度下降法是一个本质上困难的计算问题。
新的结果表明，研究人员在特定应用中使用梯度下降法所获得的性能表现是受限的。
牛津大学的 Paul Goldberg 说：“梯度下降法表现糟糕的情况是非常值得研究的”。他与利物浦大学的 John Fearnley 和 Rahul Savani 以及牛津的 Alexandros Hollender 共同撰写了一篇关于这个问题的文章，该成果在 6 月份的 ACM Symposium on Theory of Computing（STOC，计算理论顶会之一）上获得了最佳论文奖，论文标题为 The Complexity of Gradient Descent: CLS = PPAD ∩ PLS（“数据实战派”后台回复STOC获取论文下载地址）。
你可以将函数图像想象成一个景观，在这个景观中海拔等于该特定地点的函数值（“利润”）。
在给定位置找到景观最陡的坡度方向，然后从该位置向最陡坡度的反方向搜索该景观的局部最小值，景观的坡度称为梯度，因此这种寻找最小值的方法被命名为梯度下降法。梯度下降法是现代应用研究的一个重要工具，但对于许多常见问题，梯度下降法并不能很好地解决。但在这项研究之前，并没有人全面的解释竟是什么造成了梯度下降法的使用困难，以及何时会陷入困境问题。在计算机科学的另一个领域——计算复杂性理论有助于回答这个问题。
麻省理工学院的 Costis Daskalakis 说：“许多使用梯度下降法的工作并没有涉及到复杂性理论”。
计算复杂性是对解决或验证不同计算问题的解决方案所需的资源（通常是计算时间）的研究。研究人员将问题分为不同的类别，同一类别中的所有问题都具有一些共同的基本计算特征。
举一个与新论文相关的例子，想象一个城镇，那里的人比房子多，每个人都住在一所房子里。给你一个电话簿，上面写着镇上每个人的姓名和地址，你需要找到住在同一所房子中的两个人。你一定能够找到答案，因为这里的人比房子多，但需要进行搜索（特别是当他们没有共同的姓氏时）。
这个问题属于一个称为 TFNP（Total Function Nondeterministic Polynomial）的复杂类，全名叫做“全函数非确定多项式”。它是所有计算问题的集合，这些问题保证有解决方案，并且可以快速检查其解决方案的正确性。研究人员关注 TFNP 中两个问题子集的交集。
第一个子集称为多项式局部搜索 PLS（Polynomial Local Search）。这是一系列问题的集合，涉及在特定区域中寻找函数的最小值或最大值。这些问题的答案可以通过相对直接的推理找到。
例如最佳路线规划就是一个 PLS 的问题，这使得你能够以尽可能短的旅行距离访问固定数量的城市，因为你只能通过更改旅行城市的顺序来更改行程，计算建议路线的长度十分容易。由于调整行程的方式有限制，因此你很容易就可以看出哪些路线可以缩短行程，这意味着你一定会找到一条再也无法缩短行程的路线——局部最小值。
第二个子集是有向图上的多项式奇偶校验参数问题 PPAD（Polynomial Parity Arguments On Directed Graphs）。这些问题的解决方法一个更复杂的过程，称为 Brouwer 不动点定理。这个定理说，对于任何连续函数，都有一个已知的不动点可以使函数保持不变。这在日常生活中是确实存在的，如果你搅拌一杯水，该定理保证绝对会有一个水粒子会回到它一开始所处的位置。
PLS 和 PPAD 类问题的交集组成了称为 PLS int PPAD 的一类问题。它包含众多与复杂性研究人员相关的自然问题。然而，直到目前为止，研究人员还无法找到一个完整的 PLS int PPAD 自然问题，这足以说明 PLS int PPAD 是这类问题中最难的那个。
在这篇论文提出观点之前，唯一已知完整的 PLS int PPAD 问题是人为构造出来的，这个问题同时也被称为“Either-Solution”。这个问题将一个属于 PLS 的完整问题和另一个属于 PPAD 的完整问题粘在了一起，形成了一个研究人员在自然情况下不太可能遇到的问题。
在新论文中，研究人员证明了梯度下降和 Either-Solution 方案一样是计算困难的，这说明了梯度下降法本身就是一种完整的 PLS int PPAD 问题。
哥伦比亚大学的 Tim Roughgarden 说：“我们将[计算的本质]作为一个物种尝试深入理解各种形式的东西。我认为[计算的本质]应该足以让我们对结果感到兴奋。”这并不意味着梯度下降法的表现会一直挣扎。实际上，梯度下降法对于大多数应用来说，仍然和以往一样快速有效。
Goldberg 说：“对于计算复杂性总有一种略带幽默的刻板印象，认为我们在实践中想要节省大量时间来解决一个问题，并最终被证明实际上是非常困难的”。
但这一结果说明应用研究人员不应该总是希望使用梯度下降法能够为某些对精度要求很高的问题提供准确的解决方案。
精度问题是涉及到计算复杂性的核心问题，需要首先对资源需求进行评估。在许多复杂问题中，精度和速度之间有着根本的联系。要使算法被认为是有效的，你必须首先提高解决方案的精度，而不应该为找到缩短解决方案所需时间而付出相应的高昂代价。新的研究结果表明，对于精度要求较高的应用，梯度下降法可能不是一种有效的方法。
例如，在机器学习中由于不需要极高的精度，因此梯度下降法经常被拿来使用。然而，当机器学习研究人员希望将实验的精度提高一倍时，想要得出新的结果意味着他们可能需要将梯度下降算法的运行时间增加四倍，这不是一种理想的解决方法，但同时也不会影响训练的结果。
但对于其他应用，譬如数值分析，研究人员可能需要优化精度。为实现这样的优化，他们可能必须将梯度下降的运行时间进行平方，这使得计算变得非常困难。
研究人员必须在实践中某个地方进行妥协，他们要么接受不太精确的解决方案，要么局限于容易求解的问题，要么找到一种方法能够管理较长时间的运算。
但这并不是说基于梯度下降的快速方法不存在。可能会存在，但结果确实意味着，任何基于梯度下降的算法都会暗示着 PLS int PPAD 中所有的其他问题都会有更快的解决算法，这比仅仅寻找基于梯度下降法的快速算法标准要高得多。
Daskalakis 说：“许多问题都是由于数学的进步才得以解决的，这就是为什么我们喜欢有一个更够捕捉整个交叉点复杂性的自然问题，比如梯度下降法”。