最優化問題中，牛頓法為什麼比梯度下降法求解需要的迭代次數更少？

11-24

經常看到資料上這麼寫，誰能給出詳細點的解釋，比如在幾何方面上的解釋

像@崔岩說的那樣，牛頓法是二階收斂，梯度下降是一階收斂，所以牛頓法就更快。如果更通俗地說的話，比如你想找一條最短的路徑走到一個盆地的最底部，梯度下降法每次只從你當前所處位置選一個坡度最大的方向走一步，牛頓法在選擇方向時，不僅會考慮坡度是否夠大，還會考慮你走了一步之後，坡度是否會變得更大。所以，可以說牛頓法比梯度下降法看得更遠一點，能更快地走到最底部。

根據wiki上的解釋，從幾何上說，牛頓法就是用一個二次曲面去擬合你當前所處位置的局部曲面，而梯度下降法是用一個平面去擬合當前的局部曲面，通常情況下，二次曲面的擬合會比平面更好，所以牛頓法選擇的下降路徑會更符合真實的最優下降路徑。

wiki上給的圖很形象，我就直接轉過來了：

紅色的牛頓法的迭代路徑，綠色的是梯度下降法的迭代路徑。參考：

http://en.wikipedia.org/wiki/Newton"s_method_in_optimization

金秉文說的很全面，再補充幾點：

1. 牛頓法起始點不能離局部極小點太遠，否則很可能不會收斂。(考慮到二階擬合應該很容易想像)，所以實際操作中會先使用別的方法，比如梯度下降法，使更新的點離最優點比較近，再開始用牛頓法。
2. 牛頓法每次需要更新一個二階矩陣，當維數增加的時候是非常耗內存的，所以實際使用是會用擬牛頓法。
3. 梯度下降法在非常靠近最優點時會有震蕩，就是說明明離的很近了，卻很難到達，因為線性的逼近非常容易一個方向過去就過了最優點(因為只能是負梯度方向)。但牛頓法因為是二次收斂就很容易到達了。

牛頓法最明顯快的特點是對於二階函數(考慮多元函數的話要在凸函數的情況下)，牛頓法能夠一步到達，非常有效。

牛頓法是二階收斂的，而梯度下降法是一階收斂。二階其實相當於考慮了梯度的梯度，所以相對更快。

多圖預警

本文講你肯定能懂的機器學習多維極值求解，主要講梯度下降和牛頓法的區別應該能夠完美的回答題主的問題

事先說明

本文面向學習過高等數學統計學和線性代數基礎知識的本科生，並假設讀者擁有基本的矩陣運算和求導運算的相關知識，類似梯度，方嚮導數、Hessian Matrix這些東西不懂也沒關係，我會用儘可能通俗的語言說明運算中的意義。

那麼從最簡單的開始。

梯度下降演算法

梯度是個啥？我想最開始接觸梯度的各位是在方嚮導數那一章接觸這一概念的，如果老師沒怎麼講的話可能有些人還不知道梯度是個向量。當你學梯度的時候，所有的概念全都是在二元函數下的，well，也寫想像力不是很豐富的同學可能不知道這是個啥。來，我們降維先。

多維條件下是曲面對函數的一階偏導數向量&，那麼在一維條件下梯度會是什麼的？顯然就木有偏導數了，只有一個東西，當然你也可以把它寫成向量的形式&，就是一個導數，只不過現在變成一維的了，所以方向只有倆，向左和向右。值為正的時候向右，值為負的時候向左，值大值小不影響方向隻影響距離。

在二維條件下，因為有了兩個偏導數，所以這個向量能表示一圈。如果你以前看過些文章或者視頻或者什麼ppt之類的東西，大概你會聽說一種說法：「梯度是曲面中最陡峭的方向，這個方向是下降最快的方向。」實際上這種說法是不準確的，從一維的角度來看，「梯度」其實是上升最快的方向，比如 $mathrm{y=}{mathrm{x}}^{mathrm{2}}mathrm{-}mathrm{3}$ 在 $x=2$ 處的導數是1，方向向右，這個方向函數是增長的。同樣二維也是如此。只不過大部分迭代公式中在梯度的前面會加一個負號，比如這個 $heta = heta -H^{-1}{ abla }_{ heta }J( heta )$ 。所以也就直接認為它代表了下降最快的方向了。

直觀上，你可以理解為，梯度就是一個和曲面等高線垂直的法線，沖著增高的那邊。就像下圖：

那麼它相反的方向就是下降的方向啦，函數的極值點導數都是0的，也就是說，你沿著梯度方向一直走，如果最終收斂到一個點，那肯定就是一個極值點，如果不收斂，說明可能不存在極值點哈(這裡因為有步長的涉及，在求解的時候會遇到明明有極值點卻沒有收斂的問題，後面會提到)。

舉個例子，在一維下用梯度下降演算法求解極值點的問題。這裡我先舉一個方便驗算的例子，方便大家理解。

比如方程 $y=x^2-3$ 求解極值點。當然你口算都能算出來，不要急著算結果，來理解一下梯度能幹啥。

一階導 $y$ 在 $x=1$ 的時候我們開始迭代，沿著下降最快的方向左邊一點一點移動。迭代公式 $x:= x-alpha y$ 這裡 $alpha$ 就是步長，用來調節每一次移動的距離，你也可能聽過一些 $alpha$ 不能過大也不能過小的看起來只能靠經驗的廢話。如果你是剛剛入門，可能寫點程序，然後不斷試，但是實際上較優的 $alpha$ 也是可以算的，只不過那又是另一門帶有好多論文的學科了。

不同的 $alpha$ 得到不一樣的迭代效果，收斂或者震蕩收斂，周期震蕩或者直接發散，但是有的時候，算一遍 $alpha$ 很費勁啊！這裡例子簡單，要是碰到TB級的數據那真的是要死了。這還能去試？這裡簡單的說一下怎麼設置 $alpha$ ，首先你要確定x是收斂的。所以公式 $x:= x-alpha y$ 可以寫成

${centering {egin{eqnarray}x:= x-2alpha \ =(1-2alpha )x end{eqnarray}}}$

為了收斂，其中 $-1<left(1-2alpha ight)<1$ ，然後你就知道 $0<alpha <1$ 了。

實際上 $alpha$ 如果控制在 $0$ 到 $frac{1}{2}$ 之間會收斂更快，因為震蕩收斂總會造成一些重複計算。

二維上的梯度下降能幹啥呢？

還是舉一個簡單的例子，這裡直接連數據都是最簡單的。你有兩個點(4,4),(6,5)，你想畫一條線使得線和兩個點之間的距離平方和最小，當然你也可以口算出來，但是我們依然是為了看一下作用，直接寫公式對於一些人來說真的會蒙。

設直線的方程為 $y=kx+b$

目標函數 $Jleft(k,b ight)={left(kx_1+b-y_1 ight)}^2+(kx_2+b-y_1)^2$

偏導數

$J_kleft(k,b ight)=2left(kx_1+b-y_1 ight)x_1+2left(kx_2+b-y_2 ight)x_2 \ J_bleft(k,b ight)=2left(kx_1+b-y_1 ight)+2left(kx_2+b-y_2 ight)$

迭代公式

$left[ egin{array}{c} k \ b end{array} ight]:= left[ egin{array}{c} k \ b end{array} ight]-alpha left[ egin{array}{c} J_kleft(k,b ight) \ J_b(k,b) end{array} ight]$

同樣這裡可以計算一下 $alpha$ 的範圍

對於k

$k:=k-alpha [2left(kx_1+b-y_1 ight)x_1-2left(kx_2+b-y_2 ight)x_2] \ =k-2alpha kleft(x^2_1+x^2_2 ight)-2alpha left[x_1left(b-y_1 ight)+x_2left(b-y_2 ight) ight] \ =[1-2alpha left(x^2_1+x^2_2 ight)]k-2alpha left[x_1left(b-y_1 ight)+x_2left(b-y_2 ight) ight]$

然後 $-1<1-2alpha left(x^2_1+x^2_2 ight)<1$ 得到 $0<alpha <frac{1}{left(x^2_1+x^2_2 ight)}$

同樣如果在不允許震蕩的情況下 $0<alpha <frac{1}{2}*frac{1}{left(x^2_1+x^2_2 ight)}$

對於b

$b:=b-2alpha left(kx_1+b-y_2 ight)-2alpha left(kx_2+b-y_2 ight)\ =(1-4alpha )b-2alpha left(kx_1+kx_2-y_1-y_2 ight)$

這裡求得允許 $0<alpha <frac{1}{2}$ 並且在 $left(0, frac{1}{4} ight)$ 區間內不會震蕩，梯度計算方向在二維曲面震蕩起來長啥樣啊。來來來畫個圖。開始震蕩的部分我想我得給他個特寫。

不過癮？來看這個

大致知道啥意思就行了哈。

在不震蕩的情況下就顯得特別簡潔了。一條線走回去。

當然教科書上數學書上肯定不會這麼寫例子，為了公式的簡潔，最後改為:

對於已知的一系列點 $x=left[x_1,x_2,dots ,x_n ight], y=left[y_1,y_2,dots ,y_n ight]$

目標函數 $Jleft( heta ight)={frac{1}{2}{sum}}^n_{i=1}{left(fleft(x_i; heta ight)-y_i ight)}^2$

其中的 $fleft( heta ;x_i ight)$ 就是我們上面寫的 $kx+b$ 了, $heta$ 則表示所有參數的集合。咦？公式多了個 $frac{1}{2}$ 是哪來的？在這裡實際上這個值是多少都無所謂，因為兩個偏導數都帶著這個 $frac{1}{2}$ 不影響梯度方向，隻影響步長，而步長又可以由 $alpha$ 調節，我們可以理解為，加了它，導數寫起來好看^_^。就像下面這樣。

$[frac{partial left(J ight)}{partial left( heta ight)}={mathit{sum}}^n_{i=1}left(fleft( heta ;x_i ight)-y_i ight)frac{partial left( heta ;x_i ight)}{partial left( heta ight)}]$

迭代公式

$[ heta := heta -alpha frac{partial left(J ight)}{partial ( heta )}]$

$heta$ 就是上面寫到的 $left[ egin{array}{c} k \ b end{array} ight]$ 一個列向量

牛頓法

提到牛頓法的時候，你可能在小的時候聽說過，一個用來迭代求零點的方法，稍微提一下。

如果你要求解 $sqrt3$ 小學初中的時候你可能知道隨便取一個大於0的數和一個小於0的數，然後不斷地二分得到逼近於0的點，後來你可能知道這個利用了零點定理。你可以寫一個同樣的方程 $y=x^2-3$ 求 $y=0$ 時 $x$ 的值。取 $x_{left}=1 x_{right}=2$ 然後不斷的試值，唔~~還是來畫圖吧。

你也可以看到他們的迭代過程，當然這個不叫牛頓法，這個叫二分法，比較low哈，看到沒，震蕩了，震蕩收斂慢。

講牛頓法的時候，你可能還要明確一個概念 $dy$ 和 $mathit{Delta}y$ 的區別。前者是切線帶來的高度差，後者是函數上的高度差，只有當 $dx$ 趨近於0的時候他倆才近似。而牛頓法就是用切線來快速逼近零點的，不會震蕩呦，畫圖吧先。

看起來兩步就收斂了啊，好厲害，怎麼做到不震蕩的呢它？

因為每一步迭代移動切線與x軸交叉點的距離

這個距離怎麼算?可能你已經明白了 $mathit{Delta}y/frac{ extrm{}y}{ extrm{}x}$ ，這裡 $frac{dy}{dx}$ 就是該點的一階導數。因此迭代公式如下：

$[x:=x-frac{y}{y$

沒錯就是這麼簡單。

這裡順帶一提，對於不同的方程起始點的選擇也會影響迭代次數，如果有興趣的話可以讀一下這篇文章，看一下神奇的0x5f375a86，2次迭代求解，這裡讀兩次不讀二次^_^

那牛頓法和極值求解有關係？看起來牛頓法只能求零點啊? Naive~~，一階導零點不就是函數的極值或者駐點？

算起來更簡單，迭代公式如下

$[x:=x-frac{y$

文章是用來解釋高維極值求解的，如果你讀到這裡還是饒有興緻的話，那麼恭喜你，你的高數肯定90+，接下來要上乾貨了。

對於高維函數，用牛頓法求極值也是這個形式，只不過這裡的 $y^{$ 和 $y$ 都變成了矩陣和向量。而且你也可以想到，高維函數二階導有多個，寫成矩陣的形式就像這樣

$[H=left[ egin{array}{ccc} f_{11} dots f_{1n} \ vdots ddots vdots \ f_{n1} dots f_{nn} end{array} ight]]$

這個矩陣就是傳說中的Hessian矩陣，不是什麼拼音的簡寫。

同樣 $y$ 就變成了對所有參數的偏導數組成的向量

$[Jleft( heta ight)=left[ egin{array}{c} J_1 \ vdots \ J_n end{array} ight]]$

迭代公式

$[ heta := heta -H^{-1}J( heta )]$

其中 $H^{-1}$ 為Hessian 矩陣的逆

還是以上面的例子解，對就是只有兩個點求直線的那個，這次我們把目標函數的 $frac{1}{2}$ 加上

$J_kleft(k,b ight)={mathit{sum}}^n_{i=1}left(kx_i+b-y_i ight)x_i \ J_bleft(k,b ight)={mathit{sum}}^n_{i=1}left(kx_i+b-y_i ight)$

$J_{kk}left(k,b ight)=left(x^2_1+x^2_2 ight)=52 \ J_{kb}left(k,b ight)=left(x_1+x_2 ight)=10 \ J_{bb}left(k,b ight)=2$

$H=left[ egin{array}{cc} J_{kk} J_{kb} \ J_{kb} J_{bb} end{array} ight]$

$[H^{-1}=left[ egin{array}{cc} 0.5 -2.5 \ -2.5 13 end{array} ight]]$

迭代公式

$[left[ egin{array}{c} k \ b end{array} ight]:=left[ egin{array}{c} k \ b end{array} ight]-left[ egin{array}{cc} 0.5 -2.5 \ -2.5 13 end{array} ight]left[ egin{array}{c} J_kleft(k,b ight) \ J_bleft(k,b ight) end{array} ight]]$

來看一下效果，看起來直接一步到位啊！！！所以牛頓法求解你們也應該知道多厲害了。

難道是我初始點選的就比較接近答案？換一個大一點的(100,100)，依然非常快！

這麼快的原因，可能跟方程有關，換了其他方程也許就不這樣了。當然你讀到這裡也許會迫不及待的去找些自己想分析的數據，計算些參數，如果數據量少，幾百個，沒問題，幾萬個，還撐得住，要是直接從統計局或者人口普查中進行分析的話，算一個 $J_{kk}left(k,b ight)$ 可能都很慢，而且數超大。

簡單的解決辦法，有一種叫做批迭代的方法，不管是在梯度計算極值還是在牛頓計算極值上都是可行的，就是假設失去大部分點對準確度沒有太大的影響，比如說3個在一條直線上的點，去掉一個也沒什麼關係，最後反正還是會擬合成同一個參數。批迭代就是在眾多的點中隨機抽取一些，進行迭代計算，再隨機抽取一些再進行迭代。迭代的路徑可能不完美，但是最終還是會找到我們想要的答案。

當然還有其他更帥的解決方法，祝如DFP，BFGS，Broyden。限於篇幅，下回再講，私信知乎賬號最愛麥麗素可以得到部分計算代碼。

擴展閱讀

一個Sqrt函數引發的血案

梯度下降法步長的取值範圍

為什麼不同教材中凸函數和凹函數的定義是不同的?

監督學習應用.梯度下降

歡迎各類奇葩怪咖加我微信FavorMylikes，嘻~~~

http://weixin.qq.com/r/ZFEIEHLEjC-zrTZz9wR2 (二維碼自動識別)

梯度下降法是一次收斂沒問題，實際中用的牛頓法嚴格意義上不是二次收斂，因為步長設定的關係
ref:Convex Optimization

為了方便分析兩個問題的收斂的性能，給出如下兩個條件
1. 假設問題是無約束凸優化問題 $minimize f(x)$ ，即求凸函數 $f(x)$ 的最小值。凸優化問題是應用最廣的優化模型，因為它最容易解決，實際應用中的很多問題都是能轉化為凸優化問題的。令最優解為 $x^{*}$ ，最優值為 $p^{*} = f(x ^ {*})$
2. 進一步，假設目標函數在可行域上是強凸的，即存在 $m,M>0$ ，使得 $mI preceq abla^{2} f(x) preceq MI$ 成立

設某次迭代開始時的近似解為 $x$ ，那麼只要沒有達到最優解，本次迭代就應該產生一個新的近似解 $x^{+} = x + t Delta x$ ，其中 $Delta x$ 表示搜索方向， $t$ 是一個標量，表示步長。一般來說， $t$ 是在演算法開始時就給定的，也就是每次迭代都不變，這種方法叫精確直線搜索，但更有效的方式應該是回溯直線搜索，也就是在每次迭代時都重新算出一個 $t$ ，稍後我會簡單說明這個方法，先按下不表。我們討論的都是下降方法，那麼應該有 $f(x^{+}) < f(x)$ ，進一步根據函數的凸性可以得到 $abla f(x) ^ {T} Delta x<0$ ，這是任意一種優化方法必須滿足的條件

梯度下降法和牛頓法的區別是在 $x$ 附近選擇了不同階模型的近似。設 $x$ 附近的近似模型為 $ilde{f}(x+v)$ ，其中如果選擇一階近似，則有 $f(x+v)approx ilde{f} (x+v)=f(x) + abla f(x) ^{T}v$ ，只要 $abla f(x) ^ {T} v$ 是負的那就是下降方法，可以看出 $abla f(x) ^ {T} v$ 是 $v$ 的線性函數，只要 $v$ 選對了方向 $v$ 的長度越大那 $abla f(x) ^ {T} v$ 就越小，最後就是 $-infty$ ，這個問題就沒有意義了。所以我們必須得規範 $v$ 的長度，範數 $|cdot |$ 可以起到這個作用。所以我們可以定義一個規範化的下降方向，如下：
$Delta x_{nsd} = argmin { abla f(x) ^ {T}v:|v|=1}$

它的幾何意義是單位球上在 $- abla f(x)$ 方向上延伸最遠的向量，這種方法叫做最速下降法，如圖

定義非規範化的下降方向為 $Delta x_{sd} = | abla f(x) ^ {T} |_{*} Delta x_{nsd}$ ，其中 $|cdot |_{*}$ 表示對偶範數
如果我們選擇 $|cdot |$ 為歐幾里得範數，得到的就是梯度下降法，即 $Delta x_{sd} = - abla f(x)$

牛頓法的思路是採取二階近似，即 $f(x+v) approx ilde{f} (x+v) = f(x) + abla f(x)^{T}v+frac{1}{2}v^{T} abla ^{2}f(x)v$

這是 $v$ 的二次函數，在 $v=- abla^{2}f(x)^{-1} abla f(x)$ 時取到最小值，那麼定義 $Delta x_{nd} = - abla^{2}f(x)^{-1} abla f(x)$ ，則 $abla f(x)^{T} Delta x_{nt}=- abla f(x)^{T} abla ^{2}f(x)^{-1} abla f(x)$ ，根據 $abla ^{2}f(x)$ 的正定性， $abla f(x)^{T} Delta x_{nt}<0$ ，符合下降方法的要求

實際上從最速下降法的角度來看，如果我們定義一種範數 $|cdot |_{ abla^{2}f(x)}$ 為 $|v |_{ abla^{2}f(x)}=(v^{T} abla^{2}f(x)^{-1}v)^{frac{1}{2}}$ ，得到的就是牛頓法

再換一個角度來看，優化 $f(x)$ 實際上就是找 $abla f(x)=0$ 的解，也就是 $abla f(x^{*})=0$ 。那麼對梯度進行一階近似，得到 $abla f(x+v) approx abla ilde{f}(x+v)= abla f(x) + abla^{2}f(x)v$ ，則 $v=Delta x_{nt}=- abla^{2}f(x)^{-1} abla f(x)$ 時 $abla ilde{f}(x+v)=0$ ，即 $x+Delta x_{nt}$ 是一個比 $x$ 更好的解

那麼牛頓法究竟好在哪裡已經很trivial了，其他人說的也很清晰，我就不贅述了

之前說了，實際應用中更多採取回溯直線搜索。這個演算法是：
給定一個下降方向 $Delta x$ ，設定參數 $alpha in (0,0.5)$ 和 $eta in (0,1)$ ，令步長 $t=1$
如果 $f(x+tDelta x)>f(x)+alpha t<br /> abla f(x)^{T}Delta x$ ，令 $t=eta t$ ，重複執行
回溯直線搜索可以避免步子太大「容易扯著」的問題，如下圖所示：

下降方法要求 $abla f(x) ^ {T} Delta x<0$ ，則 $f(x)+alpha t abla f(x) ^{T}Delta x$ 為 $t$ 的線性減函數。如果 $t$ 太大，則 $x^{+}$ 會跨過極值點， $abla f(x)$ 容易出現振蕩的現象，降低收斂速度

不用擔心演算法不會收斂， $t$ 足夠小的時候，有 $f(x+tDelta x) approx f(x) + t abla f(x) ^{T}Delta x <f(x)+alpha t abla f(x) ^{T}Delta x$

利用強凸性假設，在採用回溯直線搜索的情況下，可以得到最速下降法和牛頓法的收斂性能分析，這個推導實在是太煩了，特別是牛頓法的那個

在梯度下降法中， $f(x)$ 將以幾何級數的方式收斂到 $p^{*}$ ，即本次迭代的初始解 $x$ 和優化後的解 $x^{+}$ 滿足 $f(x^{+}) - p^{*} leq (1 - min {2malpha, 2etaalpha m/M })(f(x) - p^{*})$

事實上偶爾會有精確直線搜索性能超過回溯直線搜索的情況，但性能提升也不大。 $alpha$ 和 $eta$ 對迭代次數的影響是noticeable的，但並不是dramatically，真正麻煩的是矩陣 $abla ^{2}f(x)$ 的條件數

牛頓法迭代分成兩個過程，第一個過程是阻尼牛頓階段，第二個才是二次收斂階段。假設 $f(x)$ 滿足利普希茨條件 $| abla^{2}f(x)- abla^{2}f(y)|_{2}leq L|x-y|_{2}$ ，其中 $L$ 為常數

可以證明，存在 $eta$ 滿足 $0<eta leq m^{2}/L$ 與 $gamma>0$ ，使得
$| abla f(x)|_{2}geq eta$ 時， $f(x^{+})-f(x) leq -gamma$
$| abla f(x)|_{2} leq eta$ 時， $f(x^{(l)})-p^{*} leq frac{2m^{3}}{L^{2}}left( frac{1}{2} ight)^{2^{l-k+1}}$
其中 $k$ 代表第一次符合第二個條件時的迭代次數， $l$ 代表總迭代次數

第一個階段回溯直線搜索時步長 $t<1$ ，因此稱為阻尼牛頓階段。在第二個階段 $x$ 已經很靠近 $x^{*}$ 了，此時始終有 $t=1$ ，牛頓法的收斂會極為迅速，稱為二次收斂階段，也稱為純牛頓階段。在絕大多數的情況下，第二個階段的迭代次數不會超過五六次，這也是牛頓法相較於梯度下降法最大的優勢，而且牛頓法對高維計算的應對也非常好

下面是我們上課的一個作業，給兩個優化問題，一個是50維的一個是100維的，要求用牛頓法和梯度下降法各解一遍。曲線代表迭代次數與優化誤差的關係（需要注意到梯度下降法和牛頓法要求的迭代誤差的上限不一樣）

前面的解說很好了，在這裡我補充一些公式說明等。
在優化問題中，牛頓法與梯度下降法一般是用來求解無約束的優化問題，都是通過迭代的思想來解決問題；
Newton"s_method_in_optimization
這是維基上關於牛頓法在優化問題中的解釋；
假若目標函數為 $fleft( x ight)$ ;初始迭代點為 $x_{0}$
其牛頓法的迭代公式為： $x_{n+1} =x_{n} -frac{f^{$ ；
梯度下降法的迭代公式為：（知乎公式上沒有關於梯度的插入吧？）

首先，從計算公式上，可以看到，牛頓法對目標函數的要求比梯度下降法要求更高；牛頓法需要

在初始點領域是二階可導；而根據梯度定義，最速下降法只要求函數在初始點領域有一階偏導；
假若兩種方法都是有效的，根據收斂判斷定理；牛頓法是二階收斂，梯度下降法是線性收斂；
所以對於二次函數，牛頓法求極值一步到位；對於更高次函數，牛頓法與梯度法搜索極值的路線就可以形象地用維基上的那張圖片來形象的說明；
這也體現了牛頓法的一大優點就是它比梯度下降法更具有全局判斷能力，在二階導數的作用下，從函數的凹凸性出發，直接搜索怎樣到達極值點；而梯度法是從初始點的領域開始判斷，在局部進行最速下降方向，然後步步逼近極值；所以往往會導致梯度下降法比牛頓法迭代的次數更多；

對於某些目標函數，可導性不強，所以有簡化的牛頓法——平行弦法；
而對於某些函數，初始值的一階導數與二階導數的比並不能很好的判斷搜索方向，所以在使用牛頓法中加強了判斷準則，發展出了牛頓下山法；初始的下山因子一般是從1開始，然後減半迭代；
阻尼牛頓法應該是在牛頓下山法發展起來的吧？（這個需要高人指導我）

梯度下降法在逼近的過程，有時候會出現之字形的下降路線，增加迭代次數；
如果極值點領域處的梯度較小（應該是說鄰域內的方嚮導數都比較小吧，歡迎補充討論！！），在靠近極值點之後的下降速率很緩慢；

對於一個具體問題，可以先判斷這個目標函數的可導性與初始值問題，然後試用這幾種方法。

牛頓用到二階導數信息
梯度法只有一階但是信息
擬牛頓法也是一階信息，但是比梯度法好很多
尤其是LBFGS

都是泰勒展開的範式，就看哪個更「擬合」了。

我來補充一下哈。牛頓迭代與梯度下降法的不同之處在於多了一項二階導數。這個二階導數對演算法的影響有兩個方面，方向和大小。方向，二階導數的幾何含義是曲率，也就是迭代的時候是考慮到梯度下降的方向的。大小，每次迭代的步長是和陡度成反比的，越陡步長越小，平坦的時候步長越大。

梯度下降法一階收斂，而牛頓法最低二階收斂，具體得看f(x)在根α的epsilon鄰域最多存在幾階連續導，也就是說可能三階四階收斂，直接說牛頓法一定二階收斂不太妥當吧。

學渣如我一直是這麼理解的
剃度下降就是看到了當前下降最快的方向然後往那個方向走一小步
而牛頓法則是看到了一個近似原方程的二次方程，然後直接跳到這個二次方程的最低點，然後再重複該步驟
這樣似乎是會快一點。。

收斂方式不一樣，梯度下降法想當於是線性收斂(linearity convergence)，而牛頓法是非線性收斂(quadratic convergence)，收斂速度更快。

目標均為使代價函數最小化

梯度下降的思路：找到代價函數負梯度，走一小步。步子不能太大，否則前面梯度轉向就不好了，畢竟又沒有算二階導，這函數的梯度那，就是無法預料。

牛頓法的思路：最小化代價函數，就是求f"(x)=0時的x，每一步都努力讓f"(x)=0就好了。怎樣做到呢？求出f"(x)的變化方向，即f""(x)，讓接下來走的一步正好讓f"(x)=0即可。因此構建等式f"(x)+af""(x)=0，求出a即可。接下來讓x走a這麼長就好。

梯度下降摸著石頭過河，每一步都只敢走眼前的一小步，生怕走錯。牛頓法每一步都目的明確，直截了當，自然快。

牛頓法是二階收斂
但是注意
牛頓法都不一定跑到局部最小值有些時候都會跑到鞍點
同時
牛頓法每一步的計算代價是很大的

牛頓法的想法是在信賴域中函數就是taylor二階展式
然後去做最優化

不過牛頓法對初值的要求更為嚴格，很容易得到局部極小值

最高票答案寫道：「牛頓法在選擇方向時，不僅會考慮坡度是否夠大，還會考慮你走了一步之後，坡度是否會變得更大。」（除此之外，那個圖和wiki引用還是很棒的）
這句話並不正確，二階導數反映的是一階導數變化快慢的程度，而非其本身大小（那還是一階導數）。這其實跟物理里的加速度和速度是類似的，牛頓第二定律就是關於加速度（位移的二階導數）的。牛頓法也是二階的，有沒有發現什麼奧秘？（迷之微笑）
梯度下降法相當於知道每一點的速度求位移的改變，你不知道此時此刻的速度改變地有多快，必須走出一步去試探；牛頓法相當於知道加速度（自然也就知道速度了）求位移的改變，你就知道此時此刻的速度改變地有多快，相當於你增加了信息的維度，減少了試探的環節。

兩大優化方法與「守望先鋒」的辯證關係：

這就跟打守望先鋒一樣，你在狙敵人的時候對敵人的移動都會有預判，如果用梯度下降法預判，你只知道對手的速度而不知道他的加速度，你可能打一槍之後有很大的偏移，於是你需要多補兩槍來糾正這個偏移；而如果你用牛頓法預判對手的移動，由於你同時知道了對手的速度和加速度，你可能只需多補一槍就能擊中敵人（牛頓法仍需要多補槍是因為你只能測量切向方向的速度和加速度，而沒有測量視向方向的裝備，可以理解為維度信息缺失）。

但是牛頓法雖然收斂步數變小了，並不意味這計算一定就更快，因為它每一步需要多出了一個計算二階導數的環節，而在高維數據里運算量就增加了N^2次運算，所以差不多是，要數據的維度N &< （梯度下降法迭代步數 / 牛頓法迭代步數） - 1，牛頓法的計算效率才會有明顯優勢。
所以一般高維數據，還是梯度下降法更快。
值得注意的一點是，從公式上看，收斂的判定：梯度下降法是Loss function達到極小值，即幾乎不在變化了；
而牛頓法則是Loss function的梯度為零（其實也是Loss function達到極小值）.

很多人都說牛頓法是二階收斂，可是怎麼就沒人打個公式出來看看 =_=。單看牛頓公式不是一階收斂來著嗎！？實際情況應該是這樣的：
首先這是牛頓的基本公式：
$x_{n+1} = x_{n} - frac{f(x)}{f$
這是一階的沒錯吧。
上面這個標準式子是為了求 $f(x) = 0$ 的時候，x的值。但是在機器學習迭代收斂的時候我們用的不是這個式子。

機器學習最優化問題時，是為了求 $f$ ,極值點x。也就是實際迭代我們用的是下面這個式子：
$x_{n+1} = x_{n} - frac{f$
這樣對二階收斂就比較直觀了。

之後就是上面幾位大神說的知識了。

主要是收斂率的問題。

梯度下降法對於平滑的凸函數能夠拿到線性收斂率。

牛頓法則能夠拿到二次收斂率。

但考慮到實際問題，牛頓法需要計算Hessian，所以如果比較總時間複雜度或者running time牛頓法不一定佔優勢。此外，收斂率其實考慮的是極限情況，如果精度要求不高，梯度下降法說不定就夠用了。

請先回憶一下no free lunch定理。不對目標函數作假設(比如凸函數)而試圖解釋牛頓法比梯度下降法好，或者一般性的，一種優化演算法比另一種優化演算法好，顯然是錯的，因為前提本身就錯了。
兩種演算法都是試圖用目標函數在鄰域的屬性去估計其在整個直徑為步長的定義域中的屬性。顯然不難構造出一次項比較平滑而二次項劇烈震蕩的目標函數，你看牛頓法還好用嗎？

最速下降法收斂速度取決於hessen陣的條件數，且是一階收斂速度。牛頓法則是二階收斂速度。

牛頓法比最速下降法收斂更快也是因為它相比後者用了二階信息，而最速下降只是用了一階信息。

但當問題非凸時，最速下降法的迭代方向能保證下降性，牛頓法就不一定了。也因此基本牛頓法沒有全局收斂性。