步子太快容易牺牲精度,梯度下降复杂度这一简单道理,获严格数学证明
梯度下降是机器学习中求最小值最常用的一种算法。尽管这种算法应用广泛,但是人们关于它计算复杂度的理论研究却寥寥无几。
在今年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也存在快速算法,但寻找后者的快速算法要比前者难得多。
最后,这一问题的计算机自动证明代码已经开源,有兴趣的朋友可以前去观摩尝试。
参考链接:[1]https://www.quantamagazine.org/how-big-data-carried-graph-theory-into-new-dimensions-20210819/[2]https://www.youtube.com/watch?v=as720_SRpY0&ab_channel=SIGACTEC[3]https://arxiv.org/abs/2011.01929[4]https://github.com/jfearnley/PPADPLS/
— 完 —
本文系网易新闻•网易号特色内容激励计划签约账号【量子位】原创内容,未经账号授权,禁止随意转载。
「量子位·视点」直播报名
人工智能产业化之路何去何从?清华博士、一流科技CEO在线分享,从AI的局限与能力出发、探讨人工智能的商业机会,报名~
![](https://static.kouhao8.com/upload/cunchu/cunchu7/2021-08-24/2021082419561710260.jpg)
点这里
相邻资料
最新课程
洋葱小学语文课 新版
2024-06-27浏览 76下载 59
洋葱小学数学-新版
2024-06-27浏览 83下载 15
洋葱小学-新版洋葱地理课
2024-06-27浏览 123下载 24
洋葱小学-新版洋葱实验课
2024-06-27浏览 191下载 47
青禾课堂金波四季美文
2024-06-27浏览 49下载 39
小E妈大语文规划
2024-06-27浏览 148下载 58
根源数学平行线数学
2024-06-27浏览 167下载 57
2024年高三高考 郑关飞政治 二轮冲刺 春季班
2024-06-27浏览 47下载 16
2024高二化学 赵晶 寒假班
2024-06-27浏览 55下载 20
2024高二化学 赵晶 春季班
2024-06-26浏览 63下载 51
栏目专题
![user-avatar](https://img.kesoso.com/uploads/allimg/20210617/1-21061H20J4K6.jpg)
Python编程
Python是多数平台上快速开发应用的编程语言。![user-avatar](https://img.kesoso.com/uploads/allimg/20210617/1-21061H04011637.jpg)
媒体引流
新媒体玩法太多,有很多方法都可以实现引流。![user-avatar](https://img.kesoso.com/uploads/allimg/20210617/1-21061H15339453.jpg)
数据库(sql,Redis,MongoDB)
数据库是一个按数据结构来存储和管理数据的计算机软件系统。![user-avatar](https://img.kesoso.com/uploads/allimg/20210617/1-21061H33F3410.jpg)
篮球
篮球是奥运会核心比赛项目,是对抗性体育运动。![user-avatar](https://img.kesoso.com/uploads/allimg/20210619/1-210619235033400.jpg)