梯度下降法 数学家澄清了现代应用中最重要的算法的本质

majer @ 2021.08.24 , 16:39

现代应用研究的许多方面都依赖于一种叫做梯度下降的关键算法。这是一个通常用于寻找特定数学函数的最大或最小值的程序——过程被称为优化函数。它可以用来计算任何东西,从制造产品的最优流程到给工人分配班次的最佳方式。

然而,尽管有如此广泛的用途,研究人员从未完全理解该算法在哪些情况是病态的。现在,新的工作解释了这一点,确立了梯度下降法的本质就是解决一个某类困难计算问题,进而找到它最勉为其难的应用场合。

牛津大学的Paul Goldberg说:"它有最坏情况,值得了解。"他与利物浦大学的John Fearnley和 Rahul Savani以及牛津大学的Alexandros Hollender是论文的共同作者。他们的工作在6月份年度计算理论研讨会上获得了最佳论文奖。

你可以把一个函数想象成一个地貌景观,土地的海拔等于函数在那个特定地点的价值("利润")。梯度下降法寻找函数的局部最小值,方法是在给定的位置寻找最陡峭的上升方向,并从该方向往下搜索。景观的坡度被称为梯度,因此被称为梯度下降。

梯度下降法是现代应用研究的一个重要工具,但有许多常见的问题,它的效果并不好。但是在这项研究之前,数值计算专家对究竟是什么原因使梯度下降法陷入困境以及何时陷入困境并没有全面的了解。这需要另一个计算科学领域里——计算复杂性理论——的学者来回答。

麻省理工学院的Costis Daskalakis说:"梯度下降法的研究,在很多方面,都缺少复杂性理论的加盟。”

计算复杂性是对解决或验证不同计算问题的解决方案所需资源的研究,资源通常是计算时间。研究人员将问题分为不同的类别,同一类别的所有问题都有一些基本的计算特征。

举个与新论文相关的例子——想象一个人比房子多的城镇,每个人都住在一个房子里。给你一本有镇上每个人的名字和地址的电话簿,让你找到住在同一所房子里的两个人。你知道你能找到答案但可能需要花点时间。

这个问题属于一个叫做TFNP的复杂性类别,即 "总函数非确定性多项式" 的简称。它是所有保证有解的计算问题的集合,其解可以快速检查正确性。研究人员专注于TFNP中两个问题子集的交集。

第一个子集被称为PLS(多项式局部搜索)。这是一个问题的集合,涉及在一个特定区域内寻找一个函数的最小值或最大值。这些问题保证有答案,可以通过相对直接的推理找到。

属于PLS类别的一个问题是规划一条路线,使你能以最短的旅行距离访问一些固定数量的城市,因为你只能通过改变旅行中任何一对连续城市的顺序来改变行程。很容易计算出任何建议路线的长度,而且,由于对你调整行程的方式有限制,很容易看出哪些改变会缩短行程。你最终必然能找到一条无法用可接受的举动来进一步改善的路线——一个局部最小值。

第二个问题子集是PPAD(有向图上的多项式奇偶性论证)。这些问题的解决方案是由一个更复杂的过程产生的,这个过程应用所谓的布劳威尔的不动点定理。该定理说,对于任何连续函数,保证有一个点是该函数的值保持不变。这在日常生活中是真实的。如果你搅动一杯水,该定理保证绝对会有一个水分子最终会停留在它最开始在的地方。

PLS和PPAD类的交集本身形成了一类被称为PLS int PPAD的问题。它包含了许多与复杂性研究者相关的自然问题。然而,直到现在,研究人员还无法找到一个对PLS int PPAD来说自然的完全问题——这意味着它是属于这类问题中最难的一个例子。

在这篇论文之前,唯一已知的PLS int PPAD完全问题是一个相当造作的问题——有时被称为 "Either-Solution" 的问题。这个问题将PLS中的一个完全问题和PPAD中的一个完全问题拼接在一起,形成了一个在研究背景之外不太可能遇到的问题。在新的论文中,研究人员证明了梯度下降和Either-Solution一样难,所以 梯度下降法本身就是PLS和PPAD的完全问题。

这并不意味着梯度下降法会一直病态。事实上,对于大多数用途来说,它和以前一样快速和有效。

Goldberg说:"关于计算复杂性有一个略带幽默的刻板印象,即我们最终所做的往往在证明一个在实践中很多时候都能解决的问题,实际上是非常困难的。"

但这一结果确实意味着应用研究人员不应该期望梯度下降能够为一些精度很重要的问题提供精确的解。

精度问题涉及到计算复杂性的核心问题--对资源需求的评估。在许多复杂性问题中,精度和速度之间存在着基本的联系。要使一个算法被认为是有效的,你必须能够提高一级的精度,又不需要在时间上付出相应的高代价。这个新结果意味着,对于需要非常精确的解决方案的应用,梯度下降可能不是一个可行的方法。

他们必须,而且在实践中也确实在某处作出妥协。他们要么接受一个不那么精确的解,要么将自己限制在稍微容易的问题上,要么找到一种方法来管理一个不方便的运行时间。

但这并不是说梯度下降的快速算法不存在。它可能存在。但这一结果确实意味着,任何这样的算法将立即意味着PLS和PPAD中所有其他问题的快速算法的存在——这比仅仅找到梯度下降的快速算法本身要重大得多。

"这就是为什么我们喜欢有一个非常自然的问题,如梯度下降法,它是整个交叉学科的复杂性的纲,纲举则目张。"

https://www.quantamagazine.org/computer-scientists-discover-limits-of-major-research-algorithm-20210817/

(0)

相关推荐

  • 复杂性中的思维(3)

    神经态空间的原型概念,允许某些有趣的认知过程解释.当输入印象只是部分地给出时,一个网络如何能够认知一个模式呢?对于动物在野外的生存来说,矢量完善的任务是至关重要的.让我们想像一下,一只沙漠中的郊狼察觉 ...

  • LaTeX中的数学公式的初步使用

    数学公式初步使用代码及注释: 显示效果: __EOF__ 本文作者:北漂的尘埃 本文链接:https://www.cnblogs.com/shizhe99/p/14042313.html 关于博主:评 ...

  • To P or not to P——这是最伟大的计算机数学问题

    2000年5月24日,新罕布什尔州的克莱数学研究所列出了数学和计算机科学中七个未解决的问题.解决其中任何一个问题的奖励是该研究所提供的一张100万美元的支票.然而,直到今天,这些问题中只有一个被解决了 ...

  • 精品公开课 | 随机梯度下降算法综述

    简介:梯度下降法 随机梯度下降 随机梯度下降的问题与挑战 随机梯度下降的优化算法(本文主要内容) 并行与分布式架构 随机梯度下降的其他优化方法 随机梯度下降法主要为了解决第一个问题:梯度计算 由于随机 ...

  • 步子太快容易牺牲精度,梯度下降复杂度这一简单道理,获严格数学证明

    本文经AI新媒体量子位(ID:QbitAI)授权转载 晓查 发自 凹非寺 梯度下降是机器学习中求最小值最常用的一种算法.尽管这种算法应用广泛,但是人们关于它计算复杂度的理论研究却寥寥无几. 在今年AC ...

  • 不能兼顾速度与精度,利物浦大学、牛津大学揭示梯度下降复杂度理论,获STOC 2021最佳论文

    机器之心报道 机器之心编辑部 梯度下降算法具有广泛的用途,但是关于它的计算复杂度的理论研究却非常少.最近,来自利物浦大学.牛津大学的研究者从数学的角度证明了梯度下降的计算复杂度,这项研究也入选 STO ...

  • 著名数学家杨乐院士:中国将成为数学强国

    采写|章剑锋 出品|网易科技<科学大师>栏目 杨乐,著名数学家.中国科学院院士,当今的普通大众不一定知道他,但他的背景,却很不一般. 他是著名数学家陈景润的同事,是中国现代数学先驱之一熊庆 ...

  • 数学家首次证明了湍流中的一个关键定律

    数学家首次证明了湍流中的一个关键定律

  • 总结分析 │如何理解“澄清”,评标环节中如何澄清?

    评标过程中的澄清 评标过程中的澄清,是指评标委员会要求投标人对投标文件中特定内容进行解释.说明.该操作一方面有利于评标委员会准确地理解投标文件的内容,把握投标人的真实意思表示,从而对投标文件做出更为公 ...

  • 梯度下降法的三种形式BGD、SGD以及MBGD

    阅读目录 1. 批量梯度下降法BGD 2. 随机梯度下降法SGD 3. 小批量梯度下降法MBGD 4. 总结 在应用机器学习算法时,我们通常采用梯度下降法来对采用的算法进行训练.其实,常用的梯度下降法 ...

  • 如何理解梯度下降法?

    梯度下降法是用来计算函数最小值的.它的思路很简单,想象在山顶放了一个球,一松手它就会顺着山坡最陡峭的地方滚落到谷底: 凸函数图像看上去就像上面的山谷,如果运用梯度下降法的话,就可以通过一步步的滚动最终 ...

  • ML之UliR:利用非线性回归,梯度下降法(迭代十万次)求出学习参数θ,进而求得Cost函数最优值

    ML之UliR:利用非线性回归,梯度下降法(迭代十万次)求出学习参数θ,进而求得Cost函数最优值 输出结果 更新-- 代码设计 import numpy as np import random de ...

  • 用Excel体验梯度下降法

    公众号后台回复"图书",了解更多号主新书内容 作者:气象学渣 来源:气象学渣 梯度下降法是目前神经网络训练过程中最为核心的算法之一,配合链式求导可实现误差在神经网络中的反向传播,更 ...

  • 梯度下降法的关键点

    梯度下降法的关键点 梯度下降法沿着梯度的反方向进行搜索,利用了函数的一阶导数信息.梯度下降法的迭代公式为: 根据函数的一阶泰勒展开,在负梯度方向,函数值是下降的.只要学习率设置的足够小,并且没有到达梯 ...

  • 如何理解“澄清”,评标环节中如何澄清?

    总结分析 │如何理解"澄清",评标环节中如何澄清? 中国招标公共服务平台 7月29日 评标过程中的澄清 评标过程中的澄清,是指评标委员会要求投标人对投标文件中特定内容进行解释.说明 ...