他们得到梯度下降算法的计算复杂度等于两类计算机问题的交集

梯度下降是机器学习中最常用的求最小值的算法之一虽然该算法被广泛使用，但对其计算复杂度的理论研究却很少

在今年由ACM举办的STOC计算机理论峰会上，来自牛津大学和利物浦大学的学者证明了这个理论问题的答案。

他们得到梯度下降算法的计算复杂度等于两类计算机问题的交集。

这篇文章也成为了STOC 2021的最佳论文。

梯度下降的复杂性

第一个子集叫做PLS。

这是一系列问题，涉及到在特定区域内寻找函数的最小值或最大值。

PLS的一个典型例子就是规划一条路线的任务，途经一些路线最短的城市，只有切换城市的顺序才能改变行程。

通过调整顺序，很容易看出哪些路线缩短了行程，最终会找到某一条路线，无法进一步缩短行程这条路线X是你需要找到的最小值

用数学公式表示:表示改变X得到的新路线)

TFNP问题的第二个子集是PPAD(有向图上的多项式奇偶校验参数)。

这个问题的解来自一个更复杂的过程，比如Brouwer不动点定理，即对于满足一定条件的连续函数，有一个点保持不变。

比如你搅拌一杯水，布劳威尔不动点定理保证水分子一定会回到原来的位置。

用数学公式来表达就是:

在实际应用中，我们不可能找到上述两个问题的绝对精确解，只要误差小于规定值，即:

PLS和PPAD的交集本身就形成了一种叫PLSPPAD的问题。

可是，直到现在，研究人员还没有找到PLSPPAD完全问题的自然例子所谓完全问题，是某种问题中最典型，最困难的问题

现在，牛津大学和利物浦大学的学者终于发现梯度下降问题(GD)相当于PLS和PPAD的交集。

PPADPLS是一类可以通过对有界区域进行梯度下降来解决的问题。

PLS和PPAD的交集被证明等价于CLS(连续局部搜索问题)

PLS和PPAD的非此即彼解就是PLSPPAD完全问题的解。

这里，梯度下降算法和这两个问题有什么联系。

请看梯度下降算法的迭代公式:

在解决实际问题时，我们也在寻找局部最小值的近似解。我们可以设置两个计算终止条件:

1.如果x’和x的损失函数小于精度:

然后终止计算，这类似于PLS中的真实—局部—最优选择问题。

2.如果x’和x之间的空间距离小于精度:

然后终止计算，这类似于PPAD的Brouwer不动点问题。

第一个相当于PLS，第二个相当于PPAD。

这一结果意味着梯度下降算法的精度和速度之间存在基本关系为了获得更高的精度，计算时间会不成比例地快速增加

精度和时间的平衡点

事实上，吴恩达在自己的机器学习课程中已经指出，梯度下降算法的计算复杂度与步数n的平方成正比。

如果精度高，需要将学习速率设置得更小。

如果机器学习研究人员可能想要将实验的准确率提高2倍，那么他们可能需要将梯度下降算法的运行时间提高4倍。

这表明在实践中必须做出一些妥协要么接受不太高的精度，要么花更长的运行时间作为交换

例如，一些加速SGD的优化算法收敛速度较快，但很可能陷入局部极小为了得到更高精度的结果，往往需要返回到SGD

对于一些具有重要精度的问题，运行时间会使梯度下降算法不可行。

但这并不是说梯度下降没有快速算法，但如果有这样的算法，那就意味着PLSPPAD也有快速算法，但找到后者的快速算法要比前者困难得多。

最后电脑自动证明这个问题的代码已经开源，感兴趣的朋友可以去观察试试。

参考链接: