300年后牛顿法得到改进，修改泰勒展开式，收敛速度更快

选自量子杂志

作者：Kevin Hartnett

机器之心编译

几乎每一天，研究人员都在寻找最优解。他们可能需要确定大型航空枢纽的最佳选址，或者如何在投资组合中最大化收益的同时最小化风险，又或者开发能够区分交通灯和停车标志的自动驾驶汽车。

从数学角度来看，这些问题都可转化为对函数最小值的搜索。

但在所有这些场景中，函数都过于复杂，无法直接评估。研究人员不得不采用近似方法求取极值。

事实证明，最有效的方法之一源自艾萨克・牛顿 300 多年前提出的牛顿法。这个算法相当简单，有点像蒙着眼睛在陌生的场景中寻找最低点。当你把一只脚放在另一只脚前面时，你需要的唯一信息就是你是在上坡还是下坡，坡度是在上升还是在下降。利用这些信息，你可以相对较快地得到近似最小值。

‍

在 17 世纪 80 年代，艾萨克・牛顿发明了一种寻找最优解的算法。三个世纪后，数学家们仍在使用和完善他的方法。

至今，该算法仍展现出惊人的威力 —— 从物流金融到计算机视觉乃至纯数学领域，是解决现代问题的关键工具。

但牛顿法也存在显著缺陷：并非适用于所有函数。为此，数学家们持续优化该技术，在保持计算效率的同时不断拓展其应用边界。

去年夏天，三位研究人员对牛顿法进行了改进，他们分别是来自普林斯顿大学的教授 Amir Ali Ahmadi，佐治亚理工学院博士后研究员 Abraar Chaudhry（曾经是 Amir Ali Ahmadi 的学生），以及耶鲁大学博士后研究员 Jeffrey Zhang，这三人将牛顿法扩展到迄今为止最广泛的函数类别，使其能够高效运行。

• 论文地址：https://arxiv.org/pdf/2311.06374

• 论文标题：Higher-Order Newton Methods with Polynomial Work per Iteration

寻找最小值

通常，数学中的函数是将输入值转化为输出值，函数最关键的特征之一是其最小值。

但找到最小值的过程充满挑战，例如函数可能包含数十个高次幂变量，使公式化分析难以实现。

早在 17 世纪 80 年代，牛顿就发现：即便面对极其复杂的函数，我们始终能获取两类关键信息来定位最小值。首先是函数的一阶导数（即斜率），反映特定点位的函数变化陡峭程度；其次是斜率自身的变化率（二阶导数），揭示函数曲率的变化特征。

Amir Ali Ahmadi 

假设你要寻找某个复杂函数的最小值。首先，选择函数上一个你认为可能接近真实最小值的点。计算该点处函数的一阶导数和二阶导数。这些导数可以用来构建一个特殊的二次方程 —— 如果函数处于二维平面中，这是一个抛物线；如果函数是更高维度的，这是一个类似杯子形状的抛物面，这个二次方程被称为泰勒近似。

现在，计算这个二次方程的最小值，而不是原来的复杂函数 —— 这是很容易做到的。然后，将这个点的坐标重新代入原来的函数，你会得到函数上的一个新点，这个新点应该更接近函数的真实最小值。

牛顿证明了，如果你不断地重复这个过程，你最终会逐步逼近原来那个更复杂函数的最小值。不过，这种方法并不总是奏效，尤其是当你从一个距离真实最小值太远的点开始时。但大部分情况下，它是有效的，并且它有一些非常理想的特性。

诸如其他迭代方法，如梯度下降法（当今机器学习模型中使用的算法），以线性速率收敛到真实最小值。牛顿法以「二次」速率收敛到真实最小值的速度要快得多，因为它可以比梯度下降法用更少的迭代次数确定最小值。

然而，牛顿法的每次迭代比梯度下降法的迭代更耗费计算资源，这就是为什么研究人员在某些应用（如训练神经网络）中更喜欢使用梯度下降法。但牛顿法仍然非常高效，在各种情况下都很有用。

时光回溯，如果牛顿不仅仅满足于一阶和二阶导数，而是取三阶和四阶导数，他或许可以更快地编写收敛到真实最小值的方法。这将使他得到更复杂的泰勒高阶近似。

这种高阶泰勒近似，虽然超越了牛顿时代的数学框架，但其核心思想 —— 将复杂函数简化为更易处理的模型 —— 至今仍启发着现代优化理论的发展。

Ahmadi 曾说：「牛顿在二次多项式中做到了这一点。他这样做是因为没有人知道如何最小化高阶多项式」。

在此后的几个世纪里，数学家们一直致力于扩展他的方法，探索他们能从更复杂的函数泰勒近似中榨出多少信息。

例如，在 19 世纪，俄罗斯数学家帕夫努蒂・切比雪夫提出了牛顿法的一个版本，用三次方程（指数为 3）来近似函数。但当原始函数涉及多个变量时，他的算法不起作用。

在 2021 年，尤里・涅斯捷罗夫（Yurii Nesterov 现就职于布达佩斯考文纽斯大学）展示了如何用三次方程有效地近似任意数量变量的函数。尽管如此，他的方法在尝试使用四次方程、五次方程等更高阶近似时，却无法保持其效率。这一证明无疑成为了该领域的一大突破。

如今，Ahmadi、Chaudhry 和 Zhang 将尤里・涅斯捷罗夫的结果又推进了一步。他们的算法不仅适用于任意数量的变量，还能处理任意阶数的导数。此外，他们的算法在所有这些情况下都保持了高效性 —— 这在之前是无法想象的。

但首先，他们必须找到一种方法来让一个困难的数学问题变得容易得多。

Jeffrey Zhang

寻找优化空间

在数学优化的世界中，对于高次幂函数的最小值求解，目前尚无快速通用的方法 —— 这一直是牛顿法的主要局限。不过，某些特定类型的函数因其特性而易于优化。

在最新的研究中，Ahmadi、Chaudhry 和 Zhang 的研究团队证明了一个重要的发现：证明总是可以找到具有这些特征的近似方程。然后他们展示了如何调整这些方程以有效地运行牛顿法。

那什么样的性质使得一个方程易于最小化呢？关键在于两点：

• 第一，方程应该是碗状的，或「凸的」。它只有一个谷值，而不是许多谷值 —— 这意味着当你试图最小化它时，无需担心会将任意一个低谷误认为是最低点。

• 第二个性质是方程可以写成平方和。例如，，可以写成之和。

近年来，数学家已开发出针对任意高次幂函数的优化技术 —— 只要函数同时满足凸性和平方和特性。

‍

Abraar Chaudhry 和两位同事最近发现了一种改进数百年来寻找函数最小值的方法。

但这些技术始终无法与牛顿法有效兼容，因为泰勒近似在大多数情况下并不具备这些优良特性。

但 Ahmadi、Chaudhry 和 Zhang 通过引入一种称为半正定规划（semidefinite programming）的技术来对泰勒近似进行足够的调整，使其既是平方和又是凸函数，同时调整幅度不脱离它相似的原始函数。

他们本质上在泰勒展开式中添加了一个修正因子，将其变成了一个具有两个所需属性的方程。

Ahmadi 提到「我们可以稍微改变泰勒展开式，使其更容易最小化。想象一下泰勒展开式，但经过一些调整。」

他和他的同事随后表明，使用这个修改后的泰勒展开式版本（涉及任意多个导数），他们的算法仍然能够收敛到原始函数的真实最小值。更重要的是，收敛速度会随着所用导数的数量而提升：正如使用二阶导数使牛顿法以二次速率接近最小值，使用三阶导数则使研究者们能够以三次速率接近，依此类推。

通过这一创新，Ahmadi、Chaudhry 和 Zhang 成功创建了一个更强大的牛顿法版本，与以前的技术相比，它可以用更少的迭代次数达到函数的真实最小值。

与牛顿法的原始版本一样，这种新算法的每次迭代在计算上仍然比梯度下降等方法更昂贵。因此，目前这项新工作不会改变自动驾驶汽车、机器学习算法或空中交通管制系统的工作方式。在这些情况下，最好的选择仍然是梯度下降。

宾夕法尼亚大学的 Jason Altschuler 说：「优化中的许多想法需要数年时间才能完全实用。但这似乎是一个全新的视角。」

然而，随着时间的推移，如果运行牛顿法所需的基础计算技术变得更加高效 —— 即每次迭代的计算成本降低 —— 那么 Ahmadi、Chaudhry 和 Zhang 开发的算法最终可能会在包括机器学习在内的各种应用中超越梯度下降。

Ahmadi 表示「从理论上讲，我们目前的算法是更快的」，而后他进一步补充道，希望在未来 10 到 20 年内，在实践中能同样如此。

这一研究为牛顿法注入了新的活力，尽管目前尚未达到完全实用的阶段，但其潜力不容忽视。在计算技术不断进步的背景下，这一算法有望在未来成为优化领域的核心工具之一。

（文：机器之心）