设置
  • 日夜间
    随系统
    浅色
    深色
  • 主题色

步子太快容易牺牲精度,梯度下降复杂度获严格数学证明

量子位 2021/8/24 14:26:35 责编:懒猫

梯度下降是机器学习中求最小值最常用的一种算法。尽管这种算法应用广泛,但是人们关于它计算复杂度的理论研究却寥寥无几。

在今年 ACM 举办的计算机理论顶会 STOC 上,牛津大学和利物浦大学的学者们,给我们证明了这个理论问题的答案。

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

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

梯度下降的复杂度

四位作者研究人员将目光放在了 TFNP 中两个子集问题的交集。

第一个子集称为 PLS (多项式局部搜索)。

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

属于 PLS 的一个典型例子是规划一条路线的任务,以最短的路线经过一些城市,且只能通过切换城市的顺序来改变行程。

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

用数学公式来表示就是:(p 是求路线总长度的函数,g (x) 表示改变 x 得到的新路线)

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

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

例如,如果你搅动一杯水,Brouwer 不动点定理保证绝对会有一个水分子会回到它最初的位置。

用数学公式来表示就是:

实际应用中,我们不可能要求找到以上两个问题绝对精确的解,只要误差小于规定的值 ε 即可,也就是:

PLS 和 PPAD 这两类问题的交集本身形成了一类称为 PLS∩PPAD 的问题。

然而,直到现在,研究人员都无法找到 PLS∩PPAD 完全问题的一个天然的例子。所谓的完全问题,就是某类问题中最典型、最难的问题。

现在,来自牛津大学和利物浦大学的学者们终于找到了,梯度下降问题(GD)就是,它等价于 PLS 与 PPAD 的交集。

PPAD∩PLS 是可以通过在有界域上执行梯度下降来解决的所有问题的类别。

而 PLS 与 PPAD 的交集,被他们证明等价于 CLS (连续局域搜索问题)

PLS 与 PPAD 的任意解(either-solution)就是 PLS∩PPAD 完全问题的解。

到了这里,梯度下降算法与这两个问题有什么联系呢?

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

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

1、如果 x’与 x 这两个点的损失函数小于精度 ε:

那么计算终止,这与前面 PLS 中的 Real-Local-Opt 问题类似。

2、如果 x’与 x 这两个点的空间距离小于精度 ε:

那么计算终止,这与前面 PPAD 中的 Brouwer 不动点问题类似。

第一种相当于是 PLS,第二种相当于是 PPAD。

该结果意味着,梯度下降算法精度和速度之间存在基本联系,为获得更高精度,计算时间将会不成比例地迅速增长。

精度与时间的平衡点

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

若对精度要求高,需要将学习率 η 设置得更小。

如果机器学习研究者可能希望将实验的精度提高到 2 倍,那么可能不得不将梯度下降算法的运行时间增加到 4 倍。

这表明,梯度下降在实践中必须做出某种妥协。要么接受不太高的精度,要么花费更长的运行时间来换取。

例如,一些对 SGD 进行加速的优化算法,虽然收敛速度更快,但很有可能陷入局部最小值。要想获得精度更高的结果,往往必须回归到 SGD。

对于某些精度很重要的问题,运行时长会让梯度下降算法变得不可行。

但这并不是说梯度下降的快速算法不存在,但如果存在着这样的算法,将意味着 PLS∩PPAD 也存在快速算法,但寻找后者的快速算法要比前者难得多。

最后,这一问题的计算机自动证明代码已经开源,有兴趣的朋友可以前去观摩尝试。

参考链接:

  • https://www.quantamagazine.org/how-big-data-carried-graph-theory-into-new-dimensions-20210819/

  • https://www.youtube.com/watch?v=as720_SRpY0&ab_channel=SIGACTEC

  • https://arxiv.org/abs/2011.01929

  • https://github.com/jfearnley/PPADPLS/

广告声明:文内含有的对外跳转链接(包括不限于超链接、二维码、口令等形式),用于传递更多信息,节省甄选时间,结果仅供参考,IT之家所有文章均包含本声明。

相关文章

关键词:机器学习

软媒旗下网站: IT之家 最会买 - 返利返现优惠券 iPhone之家 Win7之家 Win10之家 Win11之家

软媒旗下软件: 软媒手机APP应用 魔方 最会买 要知