300年后，牛顿工具迎来新升级

Quanta Homepage

An editorially independent publication supported by the Simons Foundation.

Home Three Hundred Years Later, a Tool from Isaac Newton Gets an Update Comment

algorithms

300年后，牛顿工具迎来新升级

By Kevin Hartnett March 24, 2025 一种简单且广泛使用的数学技术，最终可以应用于解决无限复杂的问题。

Michele Sclafani for Quanta Magazine

引言

By Kevin Hartnett Contributing Writer March 24, 2025

algorithms applied math dynamical systems machine learning mathematics All topics

每天，研究人员都在寻找最优解。他们可能想弄清楚在哪里建立一个主要的航空枢纽，或者确定如何在投资组合中最大化回报同时最小化风险，又或者开发能够区分交通灯和停车标志的自动驾驶汽车。

在数学上，这些问题被转化为寻找函数的最小值。但在所有这些场景中，函数都过于复杂而无法直接评估。研究人员必须近似计算最小值。

事实证明，最好的方法之一是使用 Isaac Newton 在 300 多年前开发的一种算法。这个算法相当简单，有点像蒙着眼睛在一个不熟悉的 landscape 中寻找最低点。当你一只脚放在另一只脚前面时，你唯一需要的信息是你是在上坡还是下坡，以及坡度是在增加还是在减少。利用这些信息，你可以相对快速地获得最小值的良好近似值。

尽管非常强大——几个世纪后，Newton's method 仍然是解决当前物流、金融、计算机视觉甚至纯数学问题the crucial 的——但它也有一个明显的缺点。它并非在所有函数上都有效。因此，数学家们继续研究这项技术，寻找在不牺牲效率的情况下扩大其适用范围的不同方法。

去年夏天，三位研究人员宣布了 Newton's method 的最新改进 (opens a new tab)。普林斯顿大学的 Amir Ali Ahmadi (opens a new tab)，以及他的前学生 Abraar Chaudhry (opens a new tab)（现任职于佐治亚理工学院）和 Jeffrey Zhang (opens a new tab)（现任职于耶鲁大学），扩展了 Newton's method，使其能够高效地处理迄今为止最广泛的函数类别。

“Newton's method 在优化中有 1,000 种不同的应用，”Ahmadi 说。“我们的算法有可能取代它。”

在 17 世纪 80 年代，Isaac Newton 开发了一种寻找最优解的算法。三个世纪后，数学家们仍然在使用和改进他的方法。 Godfrey Kneller/Public Domain

一种古老的技术

数学函数将输入转换为输出。通常，函数最重要的特征是它的最小值——产生最小可能输出的输入组合。

但找到最小值是困难的。函数可以有几十个变量，并且变量是高阶的，这使得公式分析难以进行；其解的图形成为了高维 landscape，无法从鸟瞰图进行探索。牛津大学的 Coralia Cartis (opens a new tab) 说，在这些更高维度的 landscape 中，“我们想要找到一个 valley。有些是局部的 valley；另一些是最低点。你正在努力寻找这些东西，问题是：你有什么信息可以引导你找到它？”

在 17 世纪 80 年代，Newton 认识到，即使你处理的是一个非常复杂的函数，你仍然可以获得至少两个信息来帮助你找到最深的 valley。首先，你可以计算函数的所谓一阶导数，或者斜率：函数在给定点的陡峭程度。其次，你可以计算斜率本身的变化率（函数的二阶导数）。

Amir Ali Ahmadi 在他所看到的任何地方都发现了优化问题。 Archives of the Mathematisches Forschungsinstitut Oberwolfach

假设你正在尝试寻找某个复杂函数的最小值。首先，选择函数上的一个点，你认为该点可能接近真正的最小值。计算该点处函数的一阶和二阶导数。这些导数可以用于构建一个特殊的二次方程——如果你的函数存在于二维平面中，那么就是一条抛物线；如果你的函数是更高维度的，那么就是一个称为抛物面的 cuplike 形状。这个二次方程，被称为 Taylor 近似，大致类似于你所选择的点处的函数。

现在计算二次方程的最小值，而不是原始函数的最小值——这你可以很容易地使用一个著名的公式来完成。（那是因为二次方程很简单；当方程变得更复杂时，计算最小值就会变得令人望而却步。）你会得到一个点。然后将该点的坐标重新插入到你的原始函数中，你就会得到函数上的一个新点，这个新点有望更接近其真正的最小值。再次开始整个过程。

Newton 证明，如果你不断重复这个过程，你最终会找到原始的、更复杂的函数的最小值。这种方法并非总是有效，特别是如果你从距离真实最小值太远的点开始。但在大多数情况下，它是有效的。而且它有一些令人满意的属性。

Mark Belan/Quanta Magazine; Source: arxiv:2305.07512 (opens a new tab)

其他迭代方法，比如 gradient descent——当今机器学习模型中使用的算法——以线性速率收敛到真实最小值。Newton's method 以更快的速度收敛到真实最小值：以“二次”速率。换句话说，与 gradient descent 相比，它可以识别出更少迭代次数的最小值。（Newton's method 的每次迭代在计算上比 gradient descent 的迭代更昂贵，这就是为什么研究人员更喜欢 gradient descent 用于某些应用程序，比如训练神经网络。但 Newton's method 仍然非常高效，使其在各种上下文中都有用。）

如果 Newton 没有仅仅取每个点的一阶和二阶导数，而是取三阶和四阶导数，他本可以编写他的方法，使其能够以更快的速度收敛到真实最小值。这将为他提供更复杂的 Taylor 近似，其指数大于 2。但他策略的关键是将复杂的函数转换为更简单的函数。这些更复杂的 Taylor 方程超出了 Newton 在数学上的处理能力。

Jeffrey Zhang 和他的合著者以恰当的方式摆动函数，从而扩大了一种强大的优化技术的范围。 Courtesy of Jeffrey Zhang

“Newton 这样做是针对 2 阶的。他那样做是因为没有人知道如何最小化更高阶的多项式，”Ahmadi 说。

在之后的几个世纪里，数学家们致力于扩展他的方法，以探索他们可以从函数的更复杂的 Taylor 近似中提取多少信息。

例如，在 19 世纪，俄罗斯数学家 Pafnuty Chebyshev 提出了一种 Newton's method 版本，该版本使用三次方程（指数为 3）来近似函数。但当原始函数涉及多个变量时，他的算法不起作用。最近，在 2021 年，Yurii Nesterov（现在在布达佩斯科维努斯大学）证明了如何使用三次方程有效地近似计算 (opens a new tab) 任意数量变量的函数。但他的方法无法扩展为使用四次方程、五次方程等来近似函数，而不会降低效率。不过，这个证明是该领域的一个重大突破。

现在，Ahmadi、Chaudhry 和 Zhang 将 Nesterov 的结果又向前推进了一步。他们的算法适用于任意数量的变量和任意多个导数。此外，它在所有这些情况下都保持高效——这是迄今为止不可能实现的。

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

寻找摆动空间

没有快速的、通用的方法来寻找高指数函数的最小值。这始终是 Newton's method 的主要限制。但有些类型的函数具有使其易于最小化的特性。在新工作中，Ahmadi、Chaudhry 和 Zhang 证明，始终可以找到具有这些特性的近似方程。然后，他们展示了如何调整这些方程以高效地运行 Newton's method。

什么属性使方程易于最小化？两件事：首先，方程应该是碗状的，或者“凸的”。它不是有许多 valley，而是只有一个——这意味着当你尝试最小化它时，你无需担心将任意 valley 误认为是最低的 valley。

Abraar Chaudhry 和两位同事最近找到了一种改进古老方法的方法，用于寻找函数的最小值。 Camille Carpenter Henriquez

第二个属性是，该方程可以写成平方和的形式。例如，5 x 2 + 16 x + 13 可以写成和 (x + 2)2 + (2 x + 3)2 的形式。近年来，数学家们开发了一些技术，用于最小化具有任意大指数的方程，只要它们既是凸的又是平方和。然而，当涉及到 Newton's method 时，这些技术几乎没有帮助。大多数时候，你使用的 Taylor 近似不会具有这些良好的属性。

但 Ahmadi、Chaudhry 和 Zhang 发现了一种使用称为 semidefinite programming 的技术来摆动 Taylor 近似的方法，使其既是平方和又是凸的，但又不会过度摆动，使其脱离它应该近似的原始函数。

他们基本上是在 Taylor 展开式中添加了一个 fudge factor，将其变成了一个具有两个所需属性的方程。“我们可以稍微改变 Taylor 展开式，使其更易于最小化。可以想象成 Taylor 展开式，但稍微修改了一下，”Ahmadi 说。然后他和他的同事表明，使用 Taylor 展开式的这个修改版本——涉及任意多个导数——他们的算法仍然会收敛到原始函数的真实最小值。此外，收敛速度会随着所使用的导数数量而变化：正如使用两个导数允许 Newton 以二次速率接近真实最小值一样，使用三个导数使研究人员能够以三次速率接近它，依此类推。

Ahmadi、Chaudhry 和 Zhang 创建了一个更强大的 Newton's method 版本，该版本与之前的技术相比，可以在更少的迭代次数中达到函数的真实最小值。

相关文章：

1. Surprising Limits Discovered in Quest for Optimal Solutions

2. Risky Giant Steps Can Solve Optimization Problems Faster

3. How We Can Make Sense of Chaos

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

宾夕法尼亚大学的 Jason Altschuler (opens a new tab) 说：“优化领域的许多想法都需要数年才能完全付诸实践。但这似乎是一个全新的视角。”

如果随着时间的推移，运行 Newton's method 所需的底层计算技术变得更加高效——从而降低了每次迭代的计算成本——那么 Ahmadi、Chaudhry 和 Zhang 开发的算法最终可能会在各种应用（包括机器学习）中超越 gradient descent。

“从理论上讲，我们的算法现在可以被证明更快，”Ahmadi 说。他补充说，他希望在 10 到 20 年后，它在实践中也会如此。