为基于梯度的优化器提供近似梯度没用吗?

计算科学 优化
2021-12-08 06:47:00

如果只能提供数值梯度,那么使用基于梯度的优化算法是否毫无意义?如果不是,如果对优化库本身执行有限微分很简单,为什么要首先提供数值梯度?

[编辑]

  • 只是为了澄清一下,我的问题确实比特定应用程序更笼统。虽然我的应用领域恰好是各种统计框架下的似然优化。

  • 我对自动区分的问题是似乎总是有一个问题。要么 AD 库无法传播到外部库调用(如 BLAS),要么您必须彻底重做您的工作流程,以至于处理起来很痛苦……尤其是在您使用类型敏感的语言时。我对 AD 的抱怨完全是一个单独的问题。但我愿意相信!

  • 我想我需要更好地提出我的问题,但我做得很差。如果可以选择使用无导数优化算法或基于导数的优化算法,但需要注意的是我只能给它一个数值梯度,平均而言,哪一个会更好?

3个回答

如果您的目标是平滑的,那么使用导数的有限差分近似通常比使用无导数优化算法更有效。如果您有精确计算导数的代码,那么通常最好使用该代码而不是使用有限差分近似。

尽管一些优化库会使用启发式方法自动为您计算有限差分近似值来确定步长参数,但最好使用您自己的例程来计算有限差分近似值,因为您对适当的步长有更好的了解,或者因为您的代码可以利用的函数中的特殊结构。

通常值得考虑的另一个选择是使用自动微分技术来生成一个子程序,该子程序从源代码计算分析导数,以计算目标函数本身。

为了补充布赖恩的出色回答,让我提供一些(社论)背景。无导数优化方法被定义为仅使用函数评估的方法,并且基本上是“或多或少系统地对可接受集进行采样并保存最佳函数值”的所有变体 - 这就是你可以做的所有信息。这些方法大致可以细分为

  1. 随机方法,其中样本的选择基本上是随机的(这意味着随机性是一个关键组成部分;可能还有其他确定性组成部分)。这些方法通常受物理或生物过程的启发,并具有相应的名称,例如“模拟退火”、“遗传算法”或“粒子群/萤火虫/蚁丘方法”。除了“如果你尝试足够长的时间,你会以概率击中所有点(包括最小化点) ”(这是否会发生——以任何概率——在宇宙的热寂是另一回事)之外,几乎没有任何收敛理论...)作为一名数学家,我会将这些方法视为最后的手段:如果你什么都不知道1关于你的功能,这就是你所能做的,你可能会很幸运。

  2. 确定性方法,其中样本的选择不是随机的,即纯粹基于先前的函数评估。最著名的例子可能是 Nelder--Mead 单纯形法;其他人正在生成集合搜索方法。重要的是要认识到,只有在不同点的函数值之间存在任何(可利用的)关系时,这才有效——即,函数的某些平滑度。事实上,例如 Nelder-Mead 方法的收敛理论是基于构造一个非均匀的基于单纯形顶点处的函数值的梯度的有限差分逼近,并表明当单纯形收缩到一个点时,它会收敛到精确的梯度和零。(基于标准有限差分近似的变体称为罗盘搜索。)

  3. 基于模型的方法,其中函数值用于构建函数的局部模型(例如,通过插值),然后使用标准(基于梯度/Hessian)方法将其最小化。由于有限差分近似等效于多项式插值的精确导数,因此经典的“数值梯度”方法也属于此类。

如您所见,这些类之间的界限是流动的,通常只是解释问题。但是道德应该很清楚:确保使用有关要最小化的功能的所有可用信息。引用科尼利厄斯·兰佐斯的话:

任何数学技巧都无法弥补信息的缺乏。

毕竟,如果您对函数一无所知,它还可能是完全随机的,而最小化随机值是愚蠢的差事......

你的问题是关于基于梯度的优化器,所以我认为布赖恩是对的。我只会分享一些问题,因为我自己目前正在努力解决这个问题。

有限差分的问题是 1) 性能,因为您必须为每个维度重新评估函数,以及 2) 选择一个好的步长可能很棘手。如果步长太大,函数的线性假设可能不成立。如果步长太小,可能会遇到函数本身的噪声,因为导数会放大噪声。如果函数涉及求解微分方程,后者可能是一个真正的问题。如果可以分析计算梯度,或者使用灵敏度方程,它肯定会更准确,可能更快。

如果您还没有在软件上投入太多时间,您可以尝试另一种方法,那就是使用复杂的算术来运行它。称为复阶微分基本思想是当你评估函数时,如果你想要它相对于参数 X 的梯度,你将 X 的虚部设置为一个非常小的数字eps完成计算后,函数值的虚部除以eps后,就是相对于 X 的梯度。当然,当你想要相对于 Y 的梯度时,你必须再做一遍。有趣的是它的eps可以做得非常小。它起作用的原因是微积分的正常规则精确地反映在复数算术的规则中。

也就是说,我认为它不是万能的,因为在复杂的算术中做一个复杂的函数并不总是那么容易,如果可以解析计算梯度是不值得的,并且在微分方程的情况下它完全等同于灵敏度方程,我正在做必要的事情。