梯度下降使用其導數知識最大化函數。牛頓法，一種尋根算法，利用其二階導數的知識來最大化函數。當二階導數已知且易於計算時（在邏輯回歸中使用Newton-Raphson算法），可以更快。但是，二階導數的解析表達式通常很複雜或難以處理，需要大量的計算。用於計算二階導數的數值方法也需要大量計算-如果需要$ N $值來計算一階導數，則對於第二階導數需要$ N ^ 2 $。

更多人應該在機器學習中使用牛頓方法*。我是說這是一個具有數值優化背景的人，在過去的幾年中涉足機器學習。

如果正確使用牛頓法，此處（甚至在文獻中）答案的弊端就不成問題。此外，確實很重要的缺點還可以通過不那麼明顯的機制來減緩相同或更多數量的梯度下降。

• 在Wolfe條件下使用線搜索或使用或信任區域可防止收斂到鞍點。適當的梯度下降實現也應該這樣做。 Cam.Davidson.Pilon的答案中引用的論文指出了存在鞍點時“牛頓法”的問題，但他們主張的解決方法也是牛頓法。

• 使用牛頓法不需要構造完整的（密集的）Hessian。您可以使用僅使用矩陣向量乘積的迭代方法（例如共軛梯度之類的Krylov方法）將Hessian的逆應用於向量。例如，請參閱CG-Steihaug信任區域方法。

• 您可以通過求解兩個與形式已經與計算梯度的伴隨方程相同形式的高階伴隨方程，來有效地計算Hessian矩陣向量乘積（例如，神經網絡中兩個反向傳播步驟的工作培訓）。

• 病態條件減慢了迭代線性求解器的收斂速度，但同時也使梯度下降速度變慢了，甚至變差了。使用牛頓法而不是梯度下降法將難度從非線性優化階段（可以做很多事情來改善這種情況）轉移到線性代數階段（在此階段，我們可以使用數字線性代數預處理技術的整個庫來攻擊它）。

• 此外，計算從“許多便宜的步驟”轉變為“一些昂貴的步驟”，從而為子步驟（線性代數）級別的並行化提供了更多機會。

有關這些概念的背景信息，我推薦Nocedal和Wright撰寫的書“數值優化”。

*當然，牛頓的方法不能幫助您使用L1或其他類似的壓縮感測/稀疏度提升罰函數，因為它們缺乏所需的平滑度。

兩個原因的組合：

牛頓法吸引到鞍點；
• 鞍點在機器學習或實際上是任何多變量優化中很常見。

查看函數$$ f = x ^ 2-y ^ 2 $$

如果應用多元牛頓法，則會得到以下結果。 $$ \ mathbf {x} _ {n + 1} = \ mathbf {x} _n-[\ mathbf {H} f（\ mathbf {x} _n）] ^ {-1} \ nabla f（\ mathbf {x } _n）$$

讓我們得到黑森州： $$ \ mathbf {H} = \ begin {bmatrix} \ dfrac {\ partial ^ 2 f} {\ partial x_1 ^ 2} & \ dfrac {\ partial ^ 2 f} {\ partial x_1 \，\ partial x_2} & \ cdots & \ dfrac {\ partial ^ 2 f} { \ partial x_1 \，\ partial x_n} \\ [2.2ex] \ dfrac {\ partial ^ 2 f} {\ partial x_2 \，\ partial x_1} & \ dfrac {\ partial ^ 2 f} {\ partial x_2 ^ 2} & \ cdots & \ dfrac {\ partial ^ 2 f} { \ partial x_2 \，\ partial x_n} \\ [2.2ex] \ vdots & \ vdots & \ ddots & \ vdots \\ [2.2ex] \ dfrac {\ partial ^ 2 f} {\ partial x_n \，\ partial x_1} & \ dfrac {\ partial ^ 2 f} {\ partial x_n \，\ partial x_2} & \ cdots & \ dfrac {\ partial ^ 2 f} {\ partial x_n ^ 2} \ end {bmatrix}。$$

$$ \ mathbf {H} = \ begin {bmatrix} 2 & 0 \\ [2.2ex] 0 & -2 \ end {bmatrix} $$

將其反轉： $$ [\ mathbf {H} f] ^ {-1} = \ begin {bmatrix} 1/2 & 0 \\ [2.2ex] 0 & -1/2 \ end {bmatrix} $$

獲取漸變： $$ \ nabla f = \ begin {bmatrix} 2x \\ [2.2ex] -2年 \ end {bmatrix} $$

獲得最終方程： $$ \ mathbf {\ begin {bmatrix} x \\ [2.2ex] ÿ \ end {bmatrix}} _ {n + 1} = \ begin {bmatrix} x \\ [2.2ex] ÿ \ end {bmatrix} _n -\開始{bmatrix} 1/2 & 0 \\ [2.2ex] 0 & -1/2 \ end {bmatrix} \ begin {bmatrix} 2x_n \\ [2.2ex] -2y_n \ end {bmatrix} = \ mathbf {\ begin {bmatrix} x \\ [2.2ex] ÿ \ end {bmatrix}} _ n-\ begin {bmatrix} x \\ [2.2ex] ÿ \ end {bmatrix} _n = \ begin {bmatrix} 0 \\ [2.2ex] 0 \ end {bmatrix} $$

因此，您將看到牛頓法如何將您引導到$ x = 0，y = 0 $的鞍點。

相反，梯度下降法不會導致鞍點。在鞍點處，漸變為零，但是從上面的漸變中可以看到，如果稍作修改就會使優化工作無效-y變量上的漸變為負。

我最近自己學到了這一點-問題是牛頓方法想要收斂到的高維空間中鞍點的擴散。請參閱本文：識別和解決以下問題中的鞍點問題 高維非凸優化。

實際上，鞍點數與局部最小值之比增加 與維數N成指數關係。

雖然梯度下降動力學被排斥在外 通過遵循負曲率方向降低誤差的鞍點，...牛頓法不能適當地處理鞍點；如 如下所述，在馬頓動力學下，鞍點變得更具吸引力。

您問了兩個問題：為什麼沒有更多的人使用牛頓法，為什麼要使用那麼多 人們使用隨機梯度下降法嗎？這些問題有不同的答案，因為 有很多算法可以減輕牛頓方法的計算負擔 但通常比SGD更好。

首先：牛頓方法每次迭代花費很長時間，並且佔用大量內存。 正如jwimberley所指出的，牛頓方法需要計算二階導數$ H $， 這是$ O（N ^ 2）$，其中$ N $是在計算梯度時的要素數量， $ g $僅是$ O（N）$。但是下一步是$ H ^ {-1} g $，這是要計算的$ O（N ^ 3）$。 因此，在計算Hessian的成本很高時，將其求逆或求解最小二乘通常會更糟。 （如果您的功能稀疏，則漸近效果會更好，但其他方法也可以執行 更好，所以稀疏不會使牛頓相對更具吸引力。）

第二，許多方法不僅是牛頓下降法，而且比牛頓法更常用。 從某種意義上講，它們通常是牛頓方法的假裝 他們以較低的每步計算成本來近似牛頓步，但是 更多的迭代收斂。一些例子：

• 由於反轉了黑森州的費用， BFGS之類的``擬牛頓''方法近似於 inverse Hessian， $ H ^ {-1} $，通過觀察梯度在過去的變化情況 幾個步驟。

• BFGS仍然非常佔用內存 高尺寸設置，因為它需要存儲整個 $ O（N ^ 2）$近似逆黑森州。有限內存BFGS（L-BFGS）計算下一個 階躍方向為粗略的逆Hessian乘以梯度， 但這僅需要存儲最近的幾個漸變更新；它 沒有顯式存儲粗略的逆黑森州。

• 何時 您根本不想處理近似二階導數， 梯度下降法很有吸引力，因為它僅使用一階 信息。梯度下降隱式逼近逆 粗麻布作為學習率乘以單位矩陣。一世， 就個人而言，很少使用梯度下降：L-BFGS同樣容易 實現，因為它只需要指定目標函數 和漸變；它比黑森近似逆更好 梯度下降;並且由於梯度下降需要調整 學習率。

• 有時候您有很多 觀察（數據點），但您可以從中學習得差不多 較少的觀察結果。在這種情況下，您可以使用 循環通過的“批量方法”，例如隨機梯度下降 使用觀察的子集。

梯度下降方向的計算成本較低，並且在該方向上進行線搜索是向最佳方向發展的更可靠，穩定的來源。簡而言之，梯度下降相對可靠。

牛頓法相對昂貴，因為您需要在第一次迭代時計算Hessian。然後，在每個後續迭代中，您可以完全重新計算Hessian（如在牛頓方法中），或僅“更新”先前迭代的Hessian（在準牛頓方法中），這種方法便宜但不那麼可靠。

在行為特別完善的函數（尤其是二次函數完美的函數）的極端情況下，牛頓方法無疑是贏家。如果是完美的二次方，牛頓法將在一次迭代中收斂。

在功能非常差的極端情況下，梯度下降往往會勝出。它將選擇一個搜索方向，向下搜索該方向，並最終採取小而有效的步驟。相比之下，在這些情況下，牛頓法往往會失敗，特別是如果您嘗試使用準牛頓逼近。

在梯度下降和牛頓方法之間，有一些方法，例如Levenberg-Marquardt算法（LMA），儘管我看到名稱有些混淆。要點是，當事物變得混亂和混亂時，應使用更多的梯度下降信息搜索，然後在事物變得更加線性和可靠時，使用更多的牛頓法信息搜索。

對於大尺寸，Hessian通常存儲和求解成本很高 一個方向的$ Hd = g $可能會很昂貴。並行化也更加困難。

當接近解決方案時，或者如果Hessian是 緩慢變化，但需要一些技巧來解決缺乏收斂性和 缺乏確定性。

在這種情況下，通常會尋求改進，而不是精確的解決方案 牛頓或類似牛頓方法的額外成本是沒有道理的。

有多種方法可以改善上述情況，例如可變指標或 信任區域方法。

作為旁注，在許多問題中，關鍵問題是縮放和Hessian 提供了出色的縮放信息，儘管需要付費。如果可以近似於粗麻布，則通常可以大大提高性能。在某種程度上，牛頓的方法提供了“最佳”縮放比例，因為它是 仿射不變。

僅提供一些評論：

1. 一階方法在收斂和避免鞍點方面具有很好的理論保證，請參閱回溯GD和修改。
2. 回溯GD可以在DNN中實現，並且性能非常好。
3. 回溯GD可以提高學習率，當梯度較小時，可以與梯度大小成反比。當您收斂到退化的臨界點時，這非常方便。
ol>

參考：

https://github.com/hank-nguyen/MBT-optimizer

https://arxiv.org/abs/2007.03618（在這裡您還會發現一種啟發式的論點，按照Zeiler在其adadelta論文中的含義，回溯gd具有正確的單位）

關於牛頓法：如前幾次評論所指出的那樣，通過正確的修改，您可以避免出現鞍點。這是一個嚴格的證明，如果粗麻佈單數，我們還提供了一種簡單的方法進行處理

https://arxiv.org/abs/2006.01512

Github鏈接的代碼：

https://github.com/hphuongdhsp/Q-Newton-方法

尚存的問題：實施成本，無法保證收斂。

附錄：

1. LMB提到的Caplan論文：我看了一眼。我認為該論文沒有提出任何可以在O（N）中計算Hessian的算法。它只是說您只能用N個“函數求值”來計算Hessian-我還不知道這到底是什麼意思-最終的複雜度仍然是O（N ^ 2）。它還進行了一些實驗，並說通常的牛頓法在這些實驗中比（L-）BFGS更好。

2. （與上一個句子有關）。我應該將其添加為JPJ和伊麗莎白·桑托雷拉的註釋，但不能（沒有足夠的分數），因此請在此處寫：既然您提到了bfgs和l-bfgs，您可以為DNN的這些源代碼提供鏈接（例如，對於數據集MNIST，CIFAR10，CIFAR100）具有報告的實驗結果，因此人們可以與一階方法（gd的變體，包括回溯gd）進行比較，以了解它們在大規模生產中的表現如何？

ol>

UiO的Tuyen Truong

將牛頓法用於SGD有很多困難，尤其是：

• 它需要Hessian矩陣-如何估算它，例如從噪聲梯度中以合理的成本獲得足夠的精度？

• 完整的黑森州成本太高-我們寧願需要一些限制，例如到一個子空間（哪個子空間？）

• 它需要 $ H ^ {-1} $ span>，這種方法昂貴且對噪聲估計非常不穩定-可以在 $ \ lambda = 0 $ span>轉換為無窮大，

• 牛頓方法直接以零梯度吸引到閉合點...在這里通常是鞍形。如何排斥他們呢？例如。 無鞍牛頓反轉負曲率方向，但需要控制特徵值的符號

• 在線進行比較好-與其在一個點上進行大量計算，不如嘗試利用更多本地信息將其分成許多小步驟。

我們可以一步一步地從一階轉到二階，例如在動量法中僅添加3個平均值的更新，我們可以同時 MSE沿其方向擬合拋物線，以便更智能地選擇步長...在低維子空間中進行二階建模，我們仍然可以使用剩餘坐標同時進行梯度下降。