幾乎每一天，研究人員都在尋找最優(yōu)解。他們可能需要確定大型航空樞紐的最佳選址，或者如何在投資組合中最大化收益的同時(shí)最小化風(fēng)險(xiǎn)，又或者開(kāi)發(fā)能夠區(qū)分交通燈和停車標(biāo)志的自動(dòng)駕駛汽車。

從數(shù)學(xué)角度來(lái)看，這些問(wèn)題都可轉(zhuǎn)化為對(duì)函數(shù)最小值的搜索。

但在所有這些場(chǎng)景中，函數(shù)都過(guò)于復(fù)雜，無(wú)法直接評(píng)估。研究人員不得不采用近似方法求取極值。

事實(shí)證明，最有效的方法之一源自艾薩克?牛頓 300 多年前提出的牛頓法。這個(gè)算法相當(dāng)簡(jiǎn)單，有點(diǎn)像蒙著眼睛在陌生的場(chǎng)景中尋找最低點(diǎn)。當(dāng)你把一只腳放在另一只腳前面時(shí)，你需要的唯一信息就是你是在上坡還是下坡，坡度是在上升還是在下降。利用這些信息，你可以相對(duì)較快地得到近似最小值。

在 17 世紀(jì) 80 年代，艾薩克?牛頓發(fā)明了一種尋找最優(yōu)解的算法。三個(gè)世紀(jì)后，數(shù)學(xué)家們?nèi)栽谑褂煤屯晟扑姆椒ā?/span>

至今，該算法仍展現(xiàn)出驚人的威力 —— 從物流金融到計(jì)算機(jī)視覺(jué)乃至純數(shù)學(xué)領(lǐng)域，是解決現(xiàn)代問(wèn)題的關(guān)鍵工具。

但牛頓法也存在顯著缺陷：并非適用于所有函數(shù)。為此，數(shù)學(xué)家們持續(xù)優(yōu)化該技術(shù)，在保持計(jì)算效率的同時(shí)不斷拓展其應(yīng)用邊界。

去年夏天，三位研究人員對(duì)牛頓法進(jìn)行了改進(jìn)，他們分別是來(lái)自普林斯頓大學(xué)的教授 Amir Ali Ahmadi，佐治亞理工學(xué)院博士后研究員 Abraar Chaudhry（曾經(jīng)是 Amir Ali Ahmadi 的學(xué)生），以及耶魯大學(xué)博士后研究員 Jeffrey Zhang，這三人將牛頓法擴(kuò)展到迄今為止最廣泛的函數(shù)類別，使其能夠高效運(yùn)行。

• 論文地址：https://arxiv.org/pdf/2311.06374
• 論文標(biāo)題：Higher-Order Newton Methods with Polynomial Work per Iteration

尋找最小值

通常，數(shù)學(xué)中的函數(shù)是將輸入值轉(zhuǎn)化為輸出值，函數(shù)最關(guān)鍵的特征之一是其最小值。

但找到最小值的過(guò)程充滿挑戰(zhàn)，例如函數(shù)可能包含數(shù)十個(gè)高次冪變量，使公式化分析難以實(shí)現(xiàn)。

早在 17 世紀(jì) 80 年代，牛頓就發(fā)現(xiàn)：即便面對(duì)極其復(fù)雜的函數(shù)，我們始終能獲取兩類關(guān)鍵信息來(lái)定位最小值。首先是函數(shù)的一階導(dǎo)數(shù)（即斜率），反映特定點(diǎn)位的函數(shù)變化陡峭程度；其次是斜率自身的變化率（二階導(dǎo)數(shù)），揭示函數(shù)曲率的變化特征。

Amir Ali Ahmadi 

假設(shè)你要尋找某個(gè)復(fù)雜函數(shù)的最小值。首先，選擇函數(shù)上一個(gè)你認(rèn)為可能接近真實(shí)最小值的點(diǎn)。計(jì)算該點(diǎn)處函數(shù)的一階導(dǎo)數(shù)和二階導(dǎo)數(shù)。這些導(dǎo)數(shù)可以用來(lái)構(gòu)建一個(gè)特殊的二次方程 —— 如果函數(shù)處于二維平面中，這是一個(gè)拋物線；如果函數(shù)是更高維度的，這是一個(gè)類似杯子形狀的拋物面，這個(gè)二次方程被稱為泰勒近似。

現(xiàn)在，計(jì)算這個(gè)二次方程的最小值，而不是原來(lái)的復(fù)雜函數(shù) —— 這是很容易做到的。然后，將這個(gè)點(diǎn)的坐標(biāo)重新代入原來(lái)的函數(shù)，你會(huì)得到函數(shù)上的一個(gè)新點(diǎn)，這個(gè)新點(diǎn)應(yīng)該更接近函數(shù)的真實(shí)最小值。

牛頓證明了，如果你不斷地重復(fù)這個(gè)過(guò)程，你最終會(huì)逐步逼近原來(lái)那個(gè)更復(fù)雜函數(shù)的最小值。不過(guò)，這種方法并不總是奏效，尤其是當(dāng)你從一個(gè)距離真實(shí)最小值太遠(yuǎn)的點(diǎn)開(kāi)始時(shí)。但大部分情況下，它是有效的，并且它有一些非常理想的特性。

諸如其他迭代方法，如梯度下降法（當(dāng)今機(jī)器學(xué)習(xí)模型中使用的算法），以線性速率收斂到真實(shí)最小值。牛頓法以「二次」速率收斂到真實(shí)最小值的速度要快得多，因?yàn)樗梢员忍荻认陆捣ㄓ酶俚牡螖?shù)確定最小值。

然而，牛頓法的每次迭代比梯度下降法的迭代更耗費(fèi)計(jì)算資源，這就是為什么研究人員在某些應(yīng)用（如訓(xùn)練神經(jīng)網(wǎng)絡(luò)）中更喜歡使用梯度下降法。但牛頓法仍然非常高效，在各種情況下都很有用。

時(shí)光回溯，如果牛頓不僅僅滿足于一階和二階導(dǎo)數(shù)，而是取三階和四階導(dǎo)數(shù)，他或許可以更快地編寫(xiě)收斂到真實(shí)最小值的方法。這將使他得到更復(fù)雜的泰勒高階近似。

這種高階泰勒近似，雖然超越了牛頓時(shí)代的數(shù)學(xué)框架，但其核心思想 —— 將復(fù)雜函數(shù)簡(jiǎn)化為更易處理的模型 —— 至今仍啟發(fā)著現(xiàn)代優(yōu)化理論的發(fā)展。

Ahmadi 曾說(shuō)：「牛頓在二次多項(xiàng)式中做到了這一點(diǎn)。他這樣做是因?yàn)闆](méi)有人知道如何最小化高階多項(xiàng)式」。

在此后的幾個(gè)世紀(jì)里，數(shù)學(xué)家們一直致力于擴(kuò)展他的方法，探索他們能從更復(fù)雜的函數(shù)泰勒近似中榨出多少信息。

例如，在 19 世紀(jì)，俄羅斯數(shù)學(xué)家帕夫努蒂?切比雪夫提出了牛頓法的一個(gè)版本，用三次方程（指數(shù)為 3）來(lái)近似函數(shù)。但當(dāng)原始函數(shù)涉及多個(gè)變量時(shí)，他的算法不起作用。

在 2021 年，尤里?涅斯捷羅夫（Yurii Nesterov 現(xiàn)就職于布達(dá)佩斯考文紐斯大學(xué)）展示了如何用三次方程有效地近似任意數(shù)量變量的函數(shù)。盡管如此，他的方法在嘗試使用四次方程、五次方程等更高階近似時(shí)，卻無(wú)法保持其效率。這一證明無(wú)疑成為了該領(lǐng)域的一大突破。

如今，Ahmadi、Chaudhry 和 Zhang 將尤里?涅斯捷羅夫的結(jié)果又推進(jìn)了一步。他們的算法不僅適用于任意數(shù)量的變量，還能處理任意階數(shù)的導(dǎo)數(shù)。此外，他們的算法在所有這些情況下都保持了高效性 —— 這在之前是無(wú)法想象的。

但首先，他們必須找到一種方法來(lái)讓一個(gè)困難的數(shù)學(xué)問(wèn)題變得容易得多。

Jeffrey Zhang

尋找優(yōu)化空間

在數(shù)學(xué)優(yōu)化的世界中，對(duì)于高次冪函數(shù)的最小值求解，目前尚無(wú)快速通用的方法 —— 這一直是牛頓法的主要局限。不過(guò)，某些特定類型的函數(shù)因其特性而易于優(yōu)化。

在最新的研究中，Ahmadi、Chaudhry 和 Zhang 的研究團(tuán)隊(duì)證明了一個(gè)重要的發(fā)現(xiàn)：證明總是可以找到具有這些特征的近似方程。然后他們展示了如何調(diào)整這些方程以有效地運(yùn)行牛頓法。

那什么樣的性質(zhì)使得一個(gè)方程易于最小化呢？關(guān)鍵在于兩點(diǎn)：

• 第一，方程應(yīng)該是碗狀的，或「凸的」。它只有一個(gè)谷值，而不是許多谷值 —— 這意味著當(dāng)你試圖最小化它時(shí)，無(wú)需擔(dān)心會(huì)將任意一個(gè)低谷誤認(rèn)為是最低點(diǎn)。
• 第二個(gè)性質(zhì)是方程可以寫(xiě)成平方和。例如，，可以寫(xiě)成之和。

近年來(lái)，數(shù)學(xué)家已開(kāi)發(fā)出針對(duì)任意高次冪函數(shù)的優(yōu)化技術(shù) —— 只要函數(shù)同時(shí)滿足凸性和平方和特性。

Abraar Chaudhry 和兩位同事最近發(fā)現(xiàn)了一種改進(jìn)數(shù)百年來(lái)尋找函數(shù)最小值的方法。

但這些技術(shù)始終無(wú)法與牛頓法有效兼容，因?yàn)樘├战圃诖蠖鄶?shù)情況下并不具備這些優(yōu)良特性。

但 Ahmadi、Chaudhry 和 Zhang 通過(guò)引入一種稱為半正定規(guī)劃（semidefinite programming）的技術(shù)來(lái)對(duì)泰勒近似進(jìn)行足夠的調(diào)整，使其既是平方和又是凸函數(shù)，同時(shí)調(diào)整幅度不脫離它相似的原始函數(shù)。

他們本質(zhì)上在泰勒展開(kāi)式中添加了一個(gè)修正因子，將其變成了一個(gè)具有兩個(gè)所需屬性的方程。

Ahmadi 提到「我們可以稍微改變泰勒展開(kāi)式，使其更容易最小化。想象一下泰勒展開(kāi)式，但經(jīng)過(guò)一些調(diào)整?！?/span>

他和他的同事隨后表明，使用這個(gè)修改后的泰勒展開(kāi)式版本（涉及任意多個(gè)導(dǎo)數(shù)），他們的算法仍然能夠收斂到原始函數(shù)的真實(shí)最小值。更重要的是，收斂速度會(huì)隨著所用導(dǎo)數(shù)的數(shù)量而提升：正如使用二階導(dǎo)數(shù)使牛頓法以二次速率接近最小值，使用三階導(dǎo)數(shù)則使研究者們能夠以三次速率接近，依此類推。

通過(guò)這一創(chuàng)新，Ahmadi、Chaudhry 和 Zhang 成功創(chuàng)建了一個(gè)更強(qiáng)大的牛頓法版本，與以前的技術(shù)相比，它可以用更少的迭代次數(shù)達(dá)到函數(shù)的真實(shí)最小值。

與牛頓法的原始版本一樣，這種新算法的每次迭代在計(jì)算上仍然比梯度下降等方法更昂貴。因此，目前這項(xiàng)新工作不會(huì)改變自動(dòng)駕駛汽車、機(jī)器學(xué)習(xí)算法或空中交通管制系統(tǒng)的工作方式。在這些情況下，最好的選擇仍然是梯度下降。

賓夕法尼亞大學(xué)的 Jason Altschuler 說(shuō)：「優(yōu)化中的許多想法需要數(shù)年時(shí)間才能完全實(shí)用。但這似乎是一個(gè)全新的視角?！?/span>

然而，隨著時(shí)間的推移，如果運(yùn)行牛頓法所需的基礎(chǔ)計(jì)算技術(shù)變得更加高效 —— 即每次迭代的計(jì)算成本降低 —— 那么 Ahmadi、Chaudhry 和 Zhang 開(kāi)發(fā)的算法最終可能會(huì)在包括機(jī)器學(xué)習(xí)在內(nèi)的各種應(yīng)用中超越梯度下降。

Ahmadi 表示「從理論上講，我們目前的算法是更快的」，而后他進(jìn)一步補(bǔ)充道，希望在未來(lái) 10 到 20 年內(nèi)，在實(shí)踐中能同樣如此。

這一研究為牛頓法注入了新的活力，盡管目前尚未達(dá)到完全實(shí)用的階段，但其潛力不容忽視。在計(jì)算技術(shù)不斷進(jìn)步的背景下，這一算法有望在未來(lái)成為優(yōu)化領(lǐng)域的核心工具之一。