梯度下降算法具有广泛的用途，但是关于它的计算复杂度的理论研究却非常少。最近，来自利物浦大学、牛津大学的研究者从数学的角度证明了梯度下降的计算复杂度，这项研究也入选 STOC 2021 的最佳论文奖 。
当前应用研究的很多方面都依赖于一种名为梯度下降的算法。这是一个求解某个数学函数最大 / 最小值的过程（函数优化），从计算产品的最佳生产方式，到工人轮班的最佳安排方法，这一算法都能派上用场。
尽管梯度下降算法具有广泛的用途，但是关于它计算复杂度的理论研究却非常少。现在，来自利物浦大学、牛津大学等机构的研究者在论文《 The Complexity of Gradient Descent: CLS = PPAD ∩ PLS 》中给出了答案，梯度下降从本质上解决了一个非常困难的计算问题。这篇文章也入选了 STOC 2021 的最佳论文。
论文地址：https://arxiv.org/pdf/2011.01929.pdf本文作者由牛津大学的 Paul Goldberg 、Alexandros Hollender 与利物浦大学的 John Fearnley 、 Rahul Savani 共同撰写。梯度下降是现代应用研究的重要工具，但它在许多常见问题上效果不佳。在这项研究之前，并没有学者进行全面研究究竟是什么让梯度下降陷入困境，现在计算复杂性理论有助于回答这个问题。「梯度下降的很多工作都没有涉及复杂性理论，」麻省理工学院的副教授 Costis Daskalakis 说。计算复杂性是对解决或验证不同计算问题的解决方案所需资源（通常是计算时间）的研究。研究人员将问题分为不同的类别，同一类别中的所有问题共享一些基本的计算特征。举例来说，想象一个城镇，人多于房子，每个人都住在房子里。给你一本电话簿，上面写着镇上每个人的姓名和地址，你需要找到住在同一所房子里的两个人。你可以完成这个任务，不过因为人多于房子，这可能需要一些时间进行查找（特别是如果他们不共享姓氏）。上述问题属于 TFNP（total function nondeterministic polynomial） 复杂类问题。它是所有计算问题的集合，能够保证存在解决方案，并且可以快速检查解决方案的正确性。 
第一个子集称为 PLS（polynomial local search）。这是一系列问题的集合，涉及在特定区域中寻找函数的最小值或最大值， 这些问题的答案必须确保可以通过相对直接的推理找到。PLS 类别中的一个典型问题是路径规划：假如要求你以尽可能短的旅行距离访问固定数量的城市，且只能通过切换相邻城市对的顺序来改变行程。要计算所有设想路线的长度并不难，并且由于可以调整行程的方式受到限制，因此很容易看出哪些更改会缩短行程。也就是说，最终你会找到一条路线，这条路线不能再进一步缩短路程了，那么这条路线就是你要找到的最小值，就是所谓的局部极小值。TFNP 问题的第二个子集是 PPAD。这些问题的解来自更复杂的过程，称为布劳威尔不动点定理，即对于任何连续函数，存在一个点保持不变。在日常生活中也是如此，比如你搅拌一杯水，该定理保证一定有一个水分子最终会回到它开始的地方。PLS 和 PPAD 类的交集本身形成了一类称为「 PLS ∩ PPAD」 的问题。这类问题包含许多复杂性研究人员所关注的自然问题。然而，直到现在，研究人员都无法找到一个对 「 PLS ∩ PPAD」来说是完全的自然问题，所谓「完全」意味着它可能是这类问题中最难的问题。
而 PLS 与 PPAD 的交集，被他们证明等价于 CLS （连续局域搜索问题）。在这篇论文之前，唯一已知的「 PLS ∩ PPAD 」完全问题可以说是一个人工构造的问题，这个问题有时被称为「Either-Solution」。它将来自 PLS 的一个完全问题和来自 PPAD 的一个完全问题联合，形成了研究人员极少在「 PLS ∩ PPAD 」之外遇到的问题。在这篇论文中，研究人员证明了梯度下降与「Either-Solution」一样难，梯度下降本身就是「 PLS ∩ PPAD 」完全问题。
哥伦比亚大学数据科学中心教授 Tim Roughgarden 说道：「我们人类本来就应该努力去深入了解计算本质的各个方面。所以我对这项研究结果的发现感到十分兴奋。」这一发现并不意味着梯度下降会一直表现不佳。事实上，对于大多数任务来说，梯度下降与以往一样快速和高效。「关于计算复杂性有一种略带幽默的刻板印象，即我们经常会拿以前在实践中已经被解决的问题出来，然后在证明它是非常难的，」论文二作 Goldberg 说。但这一结果确实意味着，应用研究人员不应该期望梯度下降法为一些精度很重要的问题提供精确的解决方案。精度问题涉及计算复杂性的核心——资源需求的评估。在许多复杂问题中，精度和速度之间存在基本联系。要使算法被认为是有效的，你必须有能够提高解决方案的精度，而无需为找到该解决方案所花费的时间付出相应的高昂代价。新的结果也显示了，对于那些需要非常精确的解决方案的应用，梯度下降也许不是一种可行的方法。例如，梯度下降在机器学习中经常以不需要极端精确的方式使用。但机器学习研究人员想要将实验的精度提高一倍。在这种情况下，新的结果意味着他们可能需要将梯度下降算法的运行时间增加四倍。这种做法并不理想，但梯度下降还能起作用。但对于其他应用，比如在数值分析中，研究人员可能需要将精度进行成倍提升，为了实现这样的改进，他们可能必须将梯度下降的运行时间进行更多倍的提升，这样一来，计算更加难以处理。如果想要使用梯度下降，研究者必须做出妥协，要么接受精度较低的解，做一些比较简单的问题，要么找到管理冗长运行时间的方法。但这并意味着快速梯度下降算法不存在，相反，快速算法有可能存在。但这一结果暗示着「 PLS ∩ PPAD 」 的所有问题都存在快速算法，这比仅仅为梯度下降找到快速算法的难度要高得多。「数学上的进步可以解决许多现有问题，这也是为什么我们希望得到一个非常自然的问题，比如梯度下降，能够捕捉整个交叉领域的复杂性。」Daskalakis 说道。https://www.quantamagazine.org/computer-scientists-discover-limits-of-major-research-algorithm-20210817/https://www.youtube.com/watch?v=as720_SRpY0 
计算机理论顶会STOC 2021奖项出炉，滕尚华等华人学者获奖
