300年經典牛頓法，迎來重磅升級！

三位普林斯頓數學家找到更快更強的解法，其中還有一位是華人。

牛頓法是啥？學過高數的同學想必并不陌生，它通過不斷求導來尋找復雜函數f（x）接近零點的最優(yōu)解。

就是這么一個非常簡單的「近似求解」算法，因為收斂速度非常快，時至今日它仍被廣泛應用在計算機視覺、物流、金融甚至純數學問題等各個領域，比如開發(fā)能夠區(qū)分交通信號燈和停車標志的自動駕駛汽車。

但即便這么強大，牛頓法也存在一個缺點，那就是不適用于所有函數。

于是乎，過去幾個世紀諸多數學家前赴后繼企圖在此基礎之上進行優(yōu)化。現在這三位數學家成功將可適用的函數范圍一擴再擴。

比如像這個復雜的二元函數。

與傳統牛頓法相比，新方法展現出來的更連貫，覆蓋也很大。

一合著者表示，牛頓法在優(yōu)化中有1000種不同的應用，而他們的算法有可能取代它。

來看看究竟是咋回事兒。

三位數學家改寫經典牛頓法

牛頓法（Newton’s Method）誕生于17世紀，由大名鼎鼎的英國數學家牛頓首次提出。

其核心思想是，通過不斷逼近函數的根或極小值點，以尋找函數的最優(yōu)解。

通俗來說，這有點像在陌生環(huán)境里蒙眼尋找最低點。在行走過程中，我們唯一需要的信息在于兩點：1）自己是否在上坡或者下坡，即斜率（函數的一階導數）；2）以及坡度是增加還是減少，即斜率本身的變化率（函數的二階導數）。

利用上述信息，我們可以相對快速地得到一個近似值。

若將這一過程用數學方法來表示，則具體如下：

• Make a guess（做一個猜測）：選擇一個接近你認為可能是最小值的起始點，作為尋找函數最小值的起點；
• Model the curve（模擬曲線）：在該點附近構造一個拋物線，以近似原函數的形狀；
• Find the next point（找到下一個點）：計算拋物線的最低點，以此作為新的迭代點；
• Repeat（重復）：使用新的迭代點重復上述步驟，逐步逼近函數的最小值；
• Keep going（繼續(xù)進行）：持續(xù)迭代，直至找到函數的最小值。

牛頓證明了，只要不斷重復上述過程，最終就會逼近原始復雜函數的最小值。

而且和類似迭代方法（如梯度下降）相比，牛頓法雖然每次迭代的計算成本高于梯度下降，但在效率方面優(yōu)勢明顯。

簡單來說，牛頓法收斂速度相比梯度下降法更快，即在更少的迭代次數內找到最小值，因此也適用于多種情況。

不過牛頓當時也提醒：

• 雖然這一方法在大多數情況下有效，但如果一開始從一個距離真實最小值太遠的點開始，則可能越跑越偏。

而且更麻煩的是，牛頓法還存在一個顯著缺點——不適用于所有函數。

其核心策略是將一個復雜函數轉化為一個更簡單的函數，而一旦函數過于復雜，它也同樣沒轍了。

因此后來數學家們努力的方向在于，在不犧牲效率的前提下擴大算法使用范圍。

直到去年夏天，三位研究人員發(fā)表了對牛頓法的最新改進。

• 將牛頓法擴展到迄今為止最廣泛的函數類別

具體而言，他們發(fā)現牛頓法在處理某些復雜函數（如高次冪函數）時效果不好，這是因為它依賴于函數的泰勒展開（一種使用求導和多項式逼近原函數的手段），而這個展開并不總是能很好地描述原函數，特別是當函數有很多“山谷”（局部最小值）時。

于是他們提出，如果一個函數滿足兩個條件，那么它就更容易找到最小值：

• 凸形（Convex）：函數的形狀像一個碗，只有一個“山谷”
• 平方和（Sum of Squares）：函數可以表示為一些平方項的和

前者意味著如果從任何位置開始尋找，都不會陷入局部最小值的問題，因為只有一個最小值，而且無論從哪個方向開始，都會滑向這個唯一的最低點。

后者意味著可以很容易地識別和計算函數的最小值，因為平方和形式的函數特別容易處理，其平方數總是非負的，而且它們的最小值是0。

接下來，為了滿足上述條件，他們使用了一種叫做半定規(guī)劃（Semidefinite Programming）的技術來調整泰勒展開，具體步驟如下：

1、微調泰勒展開。不直接使用函數的泰勒展開，而是對其進行微調，使其既凸形又可以表示為平方和。

2、增加調整因子。在泰勒展開中加入一個調整因子，這個因子可以幫助他們控制展開的形狀，使其更接近原函數，同時滿足凸形和平方和的條件。

3、多導數收斂。他們的方法可以使用任意多個導數來進行泰勒展開，這意味著他們可以更快地找到函數的最小值。使用更多的導數可以讓算法以更高的速度（比如立方速度）收斂到最小值。

最終他們創(chuàng)造了這種更強版本的牛頓法，能夠以更少的迭代次數找到最小值。

他們的算法如下：

在下面這個函數中，與傳統牛頓法相比，其改進版本（第三階牛頓法）在理論上提供了更快的收斂速度，并且在實踐中可能比經典牛頓法更有效，尤其是在初始點離最小值點較遠的情況下。

一位華人參與

這項工作是三位數學家在普林斯頓大學期間合作完成的。

其中華人Jeffrey Zhang，目前是耶魯大學生物醫(yī)學信息學與數據科學博士后研究員，研究方向包括大型語言模型、數據科學和統計學、計算復雜性、多項式優(yōu)化、博弈論和機制設計。

此前在普林斯頓大學獲得運籌學和金融工程博士學位，導師正是同為該論文作者的Amir Ali Ahmadi教授。

更早之前，他在2014年獲得耶魯大學計算機科學和經濟學與數學學士學位。

另一位作者Abraar Chaudhry也是Amir Ali Ahmadi教授的學生，現喬治亞理工學院博士后研究員。在普林斯頓攻讀博士之前，他在布朗大學讀本科。

事實上，在這三位數學家出現之前，有很多數學家都進行了嘗試。

最早19世紀，被稱為「俄羅斯數學之父」的Pafnuty Chebyshev提出了一種牛頓法，用三次方程（指數為3）近似函數。

不過當原始函數涉及多個變量時，他的算法就會不起作用。

更近的一次，2021年俄羅斯數學家Yurii Nesterov展示了如何使用三次方程有效地逼近任何數量的變量的函數。

但他的方法無法擴展到使用四次方程、五次方程等近似函數，否則會降低其效率。

現在，3位數學家將內斯特羅夫的結果又推進了一步。

與牛頓法的原始版本一樣，這種新算法的每次迭代在計算上仍然比梯度下降等方法成本更高。

因此，目前這項新工作不會改變自動駕駛汽車、機器學習算法或空中交通管制系統的運作方式。在這些情況下，最好的選擇仍然是梯度下降。

賓夕法尼亞大學Jason Altschuler表示：許多優(yōu)化理念需要花費數年時間才能完全付諸實踐。不過這似乎是個全新的視角。

如果隨著時間的推移，運行牛頓法所需的底層計算技術變得更加高效，使得每次迭代的計算成本更低，那么Ahmadi、Chaudhry和Zhang開發(fā)的算法最終可以在包括機器學習在內的各種應用中超越梯度下降。

合著者表示，從理論上講，他們目前的算法確實更快。

論文：
https://arxiv.org/pdf/2311.06374