STOC 2021最佳论文揭示梯度下降的理论局限：精度和速度不可兼得

作者 | Nick Thieme

编译 | 陈彩娴

许多现代应用研究都对梯度下降算法有很强的依赖。梯度下降过程通常用于寻找特定数学函数中的最大值或最小值，这个过程也被称为“优化”该函数。它的计算应用十分广泛，上至研究利润最大化的产品制造方式，下至制定日常工厂工人分配轮班的最佳方式。

然而，尽管梯度下降算法的用途十分广泛，但研究人员从来没有想明白，梯度下降在什么情况下会遇到“拦路虎”？

针对这个问题，来自英国牛津大学与利物浦大学的研究团队展开了合作研究工作。他们肯定了梯度下降从本质上解决了一个十分困难的计算问题，但也指出，在某些特殊应用中，梯度下降算法的表现受到了限制。他们的工作“The Complexity of Gradient Descent: CLS = PPAD ∩ PLS”发表在理论计算机顶会 STOC 上，并获得了 STOC 最佳论文奖。

论文地址：https://arxiv.org/abs/2011.01929

1

梯度下降有多难

梯度下降是现代应用研究的重要工具，但在许多常见的问题上，它的表现并不好。在这项研究之前，研究人员并不清楚梯度下降在何时、出于何种原因而变得不再有效。针对梯度下降的局限性，计算复杂性理论的知识有利于寻找这些问题的答案。

据麻省理工学院的副教授 Costis Daskalakis 介绍，此前，许多梯度下降的研究工作都没有谈到复杂性理论。

简单来说，计算复杂性主要是研究解决或验证不同计算问题的解决方案所需要的资源（通常是计算时间）。研究人员将问题分为不同的类别，其中，同一个类别的所有问题具备同样的基本计算特征。

举一个例子：想象一个城镇，在这个城镇上，人的数量多于房子的数量，且每个人都住在一个房子里。给你一本电话簿，上面写着镇上每个人的姓名和地址，你需要找到住在同一所房子里的两个人。你知道你是可以找到答案的，因为人比房子多，但可能要查找好一会（尤其是当他们的姓氏不一样时）。

这个问题属于一个叫做“TFNP”的复杂性分类，是所有确保有解决方案、且可以快速验证解决方案是否正确的计算问题的集合。研究人员专注于研究 TFNP 中两个问题子集的交集。

第一个子集叫做“PLS”（polynomial local search，“多项式局部搜索”）。PLS问题主要是为了找到函数在特定区域中的最小值或最大值。这些问题的答案必须确保可以通过相对直接的推理找到。

路径规划任务也属于PLS分类的一个问题：假设你在旅行中只可以通过切换相邻城市对的访问顺序来改变行程，你要如何制定一条路线，使得自己可以用最短的旅行距离访问固定数量的城市。要计算所有设想路线的长度并不难；而且，由于你调整旅行线路的条件受到了限制，所以很容易看出哪些改变可以缩短旅行的距离。也就是说，你最终一定可以找到一条不需要再做出任何改进的最优路线，也就是所谓的“局部极小值”。

问题的第二个子集叫做“PPAD”（polynomial parity arguments on directed graphs，“有向图的多项式校验参数”）。这些问题的解决方案源于更复杂的解题过程，即知名的“布劳威尔不动点定理”（Brouwer’s fixed point theorem）。所谓“布劳威尔不动点定理”，就是对于任何连续函数的变换，都保证有一个点保持不变。现实中也是一样的：如果你搅拌一杯水，那么该定理保证必然会有一个水粒子的位置是不变的。

PLS 和 PPAD 分类的交集本身就形成了一类称为“PLS int PPAD”的问题。PLS int PPAD 包含了许多复杂性研究人员所关注的自然问题。然而，直到现在，研究人员也无法找到一个对 PLS int PPAD 来说是完全的自然问题——“完全”也意味着，它可能是该类中难度最高的问题。

在这篇论文发表之前，唯一已知的 PLS int PPAD 完全问题是相当人为的构造问题，有时候被称为“Either-Solution”。这个问题将来自 PLS 的一个完全问题和来自 PPAD 的一个完全问题结合，形成了极少在 PLS int PPAD 之外遇到的问题。在这篇新论文中，研究人员证明了：梯度下降与 Either-Solution 问题一样难，使梯度下降本身变成了 PLS int PPAD完全问题。

2

鱼与熊掌不可兼得

发现梯度下降的这一特点，并不代表梯度下降的表现会一直不佳。事实上，它在许多用途上都与以往一样快速、高效。

论文的二作 Paul Goldberg 谈道：“关于计算复杂性，有一个略带幽默色彩的刻板印象，就是我们经常会拎一个很久以前在实践中已经被解决的问题出来，然后证明这个问题是非常困难的。”

但这个结果确实表明，应用研究人员不应该期望梯度下降算法能够为某些对精度要求很高的问题提供十分精确的解决方案。

精度问题涉及到了计算复杂性的核心，即资源需求的评估。在许多复杂问题中，精度和速度之间存在基本联系。如果要使算法被认为是有效的，那么你必须能够在无需高成本的情况下提高解决方案的精度。新的结果也显示了，对于需要非常精确的解决方案的应用，梯度下降也许不是一种可行的方法。

例如，梯度下降通常在不要求高精度的情况下应用于机器学习，但机器学习的研究人员又可能希望将实验的精度翻倍。在这种情况下，新的研究结果表明，他们可能不得不将梯度下降算法的运行时间延长为原来的四倍。这个结果并不理想，但也不会导致梯度下降不能用。但对于其他应用，比如数值分析，由于精度要求很高，这又使得计算变得十分棘手。

就像现实落地一样，他们必须在一些地方上作出妥协，要么接受一个精度较低的解决方案，做一些比较简单的问题，要么找到有效管理冗长运行时间的方法。

但这并不是说梯度下降的快速算法不存在。相反，快速算法可能是存在的。但研究结果确实表明，如果这类快速算法存在，那么就暗示着，PLS int PPAD 的所有问题都存在快速算法——这比仅仅为梯度下降找到快速算法的难度要高得多。

Constantinos Daskalakis 总结：“许多问题可能都是基于数学进步就能解决。这也是为什么我们希望得到一个非常自然的问题，就像梯度下降一样，能够捕捉整个交叉领域的复杂性。”

雷锋网雷锋网(公众号：雷锋网)雷锋网

雷锋网特约稿件，未经授权禁止转载。详情见。