神經網路的訓練可以採用二階優化方法嗎(如Newton, Quasi Newton)？

01-07

最近在看一些關於優化理論的資料，突然想到Deep Learning里已有的演算法全都是一階梯度下降演算法的各種變形，卻從沒見過Newton或者Quasi Newton等二階方法，感覺非常奇怪，思考了一下只能想到以下幾個可能原因，不知道是否正確
1. 時間複雜度：使用二階方法通常需要直接計算或者近似估計Hessian矩陣，這部分的時間損耗使得其相比一階方法在收斂速度上帶來的優勢完全被抵消；
2. 某些非線性網路層很難（或不可能）使用二階方法優化：如果這個情況為真，那是否可能針對每個網路層使用不同的優化方案，比如像Fully-Connected Layer這樣的簡單線性映射操作使用二階方法，非線性網路層使用傳統梯度下降方法？
3. 二階方法容易被saddle points吸引，難以到達local minimal或者global minimal：NIPS 2014有篇論文([1406.2572] Identifying and attacking the saddle point problem in high-dimensional non-convex optimization)認為在高維情況下，神經網路優化最大的問題不是網路容易到達local minimal，而是容易被saddle points困住，因為在這種情況下，local minimal不管在loss值還是泛化能力上都與global minimal相差不大，反而是非常多的saddle points存在loss較高的空間中。

另外還有一個問題，為什麼SGD及其各種變種不需要做STEP LENGTH估計(WOLFE CONDITIONS)，僅通過一些相對簡單的衰減方式來決定（比如每個epoch乘以0.1）？

謝題主邀，前段較忙。強答一番，拋磚引玉。

1. 以Newton法和quasi-Newton 法為代表的二階優化方法最大的問題就是計算複雜度。以BFGS來說，一次迭代更新的複雜度是 $O(n^2)$ ，這在高維的時候是不可行的。L-BFGS使用部分梯度（最近迭代的m個梯度）來近似Hessian，複雜度是O(mn)，實際中m的取值可以是5-40. 這大大擴展了BFGS的可用範圍。具體實施中，BFGS可以應用到 $10^3-10^4$ 量級，L-BFGS可以延伸到 $10^5$ 量級。但這距離深度網路中變數的個數仍有較大差距，如AlexNet有 $6 imes 10^7$

個參數。

2. SGD在strongly convex 問題上 $f(x) - f(x_{min})$ 在 $k$ 次迭代後的值是 $O({1 over k})$ 。除非增加額外條件，這就是上界了。這裡有一個比較嚴重的問題，為了避免誤解，直接上原文（Deep Learning, Chapter 8, Optimization for Training Deep Models, http://www.deeplearningbook.org/, 第295頁）這就是說，儘管cost 可以下降的更快，但是generalization error的下降不可能超過

這就是說，儘管cost 可以下降的更快，但是generalization error的下降不可能超過 $O({1over k})$

，這樣使用超線性的優化演算法就沒有實際意義了。—— 這一段似是有問題的，請參考 @Martin Tan 在本題下的回答。（2017.2.27 注）

3.考慮cost 和樣本數量的關係。在相同計算時間（計算資源）下，使用少數樣本估計梯度從而進行多次迭代，和使用全部樣本進行單次迭代，哪一種效果更好？類似的，使用少數樣本估計的梯度進行多次迭代，和使用少數樣本估計的Hessian的L-BFGS方法，哪個效果更好？實際中，在相同的時間內使用更多的樣本信息所得的效果比使用較少樣本更好。對二階優化演算法來說，同樣的計算時間中，BFGS只能在一個mini-batch上迭代一次，而SGD能在n個mini-batch上進行迭代，後者取得的cost improvement 比前者更好。這時候，使用二階方法是不值得的。（以下截圖為上書第278頁）

4. 關於Conjugate Gradient，Momentum 和Learning Rate。在梯度法和二階方法之間有一個共軛梯度法，它使用以前的搜索信息來修正當前的梯度方向，使得搜索方向之間相互共軛

$d_k = eta_k d_{k-1} - g_k$ ,

其中 $eta_k ={ g_k ^T g_k over g_{k-1}^Tg_{k-1}}$

是共軛參數。共軛梯度法是解決大規模問題的一個理想方法，然而在神經網路的訓練中用的似乎並不多。其原因可能有二，其一，共軛梯度法嚴重依賴於線搜索，只有在準確線搜索情形才能有限次收斂。其二，當梯度本身是noise的時候，共軛參數的計算是不準確的，搜索方向之間不能保證共軛性。

這時候，一個更加簡單的方法就是使用常數的 $eta$

值，這就是momentum方法。換句話說，momentum 實際是共軛梯度法的近似 Steepest descent with momentum for quadratic functions is a version of the conjugate gradient method。Momentum的作用也和共軛梯度法的作用相似，即通過使用歷史搜索方法對當前梯度方向的修正來抵消在ill-conditioned 問題上的來回震蕩。同時，由於梯度是估計得來的，momentum對noise也有相當的效果。

由於梯度方向，momentum，和Hessian的估計都是來自於少數樣本的，含有雜訊的，那麼在這個不準確的方向上做exact line search 有多大意義呢？使用準確線搜索增加了計算的同時，可能並不能帶來足以補償的改進，反而儘可能簡單的固定learning rate或者heuristic的調整方式更加有效。上面那本書中有關於使用較大的learning rate的一些討論，認為至少訓練的開始階段，使用較大learning rate是有好處的。

說點更遠的。BP 不是一種訓練方法，而是一種計算梯度的方法，即最基本的複合函數求導。神經網路本身是一種非常結構化的複合函數，每一層複合都是矩陣乘法（線性映射）。對這樣一個具體的，結構化的問題，應該有更加專門的先進的優化方法，而不是一直固守著幾百年前的複合函數求導這樣笨拙的方法。個人淺見。

--------------------------------1月19日更新---------------------------------------

機器學習裡面使用二階優化演算法的其實也是有的，列舉幾篇

1. Hinton的學生 James Martens，主要的工作就是 Second-order Optimization for Neural Networks如Hessian-free optimization，這裡有他的文章和學位論文James Martens: Research

2. Optimization Methods for Large-Scale Machine Learning 和一個新近提出的方法https://papers.nips.cc/paper/6145-a-multi-batch-l-bfgs-method-for-machine-learning.pdf

做優化的來提供一些自己的見解：

最主要原因還是計算量太大。如果一個優化問題是 $n$ 維的，那麼單輪梯度下降的複雜度是 $O(n)$ ，Quasi-Newton是 $O(n^2)$ （當然limited-memory BFGS可以更少，但總之比梯度下降還是會高不少），而Newton method是 $O(n^3)$ 。在神經網路中， $n$ 會是神經網路中參數的個數，所以 $n$ 通常是個不小的數字（起碼也得 $10^4$ 這個量級吧），此時 $n^3$ 和 $n$ 之間的差距將非常巨大，雖然牛頓法迭代次數遠少於梯度法，但也無法彌補單輪複雜度上的巨大劣勢。實際上，正是因為大規模數據的普及，最近若干年優化演算法的研究中心也是從二階演算法回歸到了一階演算法。雖然也有不少學者試圖在大規模數據上降低二階方法的複雜度，但目前相關理論和演算法都還很不夠完善（作為做優化的人來說，個人覺得這是一個大有可為的方向）。
機器學習問題不需要高精度解。首先我反對樓上貼的Deep Learning書的那一部分內容，我認為這一段是有嚴重問題的。雖然我不是統計的專家，但據我所知，Cramer-Rao Bound刻畫的是關於樣本數量的收斂速度，而並非是關於優化演算法迭代的。此外，我翻過其中提到的引用文獻(Bottou and Bousquet, 2008)，全文中並沒有寫到不建議使用速度超過 $O(1/k)$ 的優化演算法。我認為[1]中的對於優化與泛化誤差的關係的理論分析是比較合理的：忽略常數係數以及與我們這兒討論無關的項，泛化誤差可以分解為「當前模型最優解的泛化誤差+優化誤差」，其中前一項（有些文獻叫做統計誤差）是只與模型的選擇、數據的分布、數據量的大小等相關，完全獨立於優化演算法。因此，當優化誤差已經遠低於統計誤差時，繼續優化帶來的實際收益非常小，把後一項優化誤差從 $10^{-6}$ 降到 $10^{-15}$ 可能花費大量時間，但因為前一項是一個常數，對整個泛化誤差的影響很有可能微乎其微，這是機器學習問題與優化的一些其他application很不一樣的地方。而Newton等二階演算法的一個主要優勢就是在高精度時的優化速度（比如在strongly-convex條件下，Quasi-Newton和Newton是超線性收斂的，意味著離最優點越近收斂越快），但機器學習問題對精度要求很低，優勢展現不出來。
穩定性。題主要明白的一點事，越簡單的東西往往越robust，對於優化演算法也是這樣。梯度下降等一階演算法只要步長不選太大基本都不會出問題，但二階方法遍地是坑，數值穩定性啊等等。最近我跟一位機器學習大牛討論，他就一直在跟我強調演算法的穩定性。因為現在做訓練深度神經網路很多動不動就要幾天，他們很不希望看到的一點就訓練到一半跑掛了。特別是工業界已經上線的一些實際產品，模型每天都要更新，不可能經常有人盯著，這時往往就要求訓練中不會出現任何問題。

此外，關於SGD如何選擇步長的問題，實際上這是一個非常難的問題，為什麼不能做line search樓上已經有人說過了。但仍然有不少工作在嘗試解決這個問題，例如[2,3,4]等參考文獻，題主感興趣的話可以看一看。

參考文獻：

Hardt, Moritz, Ben Recht, and Yoram Singer. "Train faster, generalize better: Stability of stochastic gradient descent." Proceedings of The 33rd International Conference on Machine Learning. 2016.
Mahsereci, Maren, and Philipp Hennig. "Probabilistic line searches for stochastic optimization." Advances in Neural Information Processing Systems. 2015.
Tan, Conghui, et al. "Barzilai-Borwein Step Size for Stochastic Gradient Descent." Advances in Neural Information Processing Systems. 2016.
Massé, Pierre-Yves, and Yann Ollivier. "Speed learning on the fly." arXiv preprint arXiv:1511.02540 (2015).

最近剛好做完一個關於隨機L-BFGS演算法的優化，也說下自己的想法。

1. 二階優化方法可以用到深度學習網路中，比如DistBelief，《Large-scale L-BFGS using MapReduce》.採用了數據並行的方法解決了海量數據下L-BFGS演算法的可用性問題。

2. 二階優化方法目前還不適用於深度學習訓練中，主要存在問題是：

1. 最重要的問題是二階方法的計算量大，訓練較慢。

2. 求導不易，實現比SGD這類一階方法複雜。

3. 另外其優點在深度學習中無法展現出來，主要是二階方法能夠更快地求得更高精度的解，這在淺層模型是有益的，但是在神經網路這類深層模型中對參數的精度要求不高，相反相對而言不高的精度對模型還有益處，能夠提高模型的泛化能力。

當然，二階優化方法也有優點，在凸優化中，訓練較SGD這類方法更為穩定更為平滑，不用調參：）

目前學術界出現了一些隨機二階優化方法，以下是比較重要的三篇，有興趣的可以看一下。

《A stochastic quasi-Newton method for large-scale optimization 》個人這篇最重要，給出了理論證明

《A Linearly-Convergent Stochastic L-BFGS Algorithm》

《A Multi-Batch L-BFGS Method for Machine Learning》

目前隨機二階優化方法主要問題是收斂速度慢，最好的隨機L-BFGS演算法為近線性收斂，與所期待的超線性收斂速度還有差距，這裡還有很多可以研究的地方，。其次是訓練不夠穩定，這裡隨機L-BFGS演算法引入了步長，其步長選擇範圍較小，易出現訓練崩潰的情況。最後通俗地解釋下，隨機方法中不使用非精確線搜索的原因：在採用batch方法中，使用非精確線搜索能夠最大化地「走」一步，這是因為採用了全局樣本信息，做出了對全局優化方向的估計。而在隨機方法中，每輪min-batch只採用了少量樣本信息，如果採用對這少量的樣本信息，用局部估計來替代全局，反而會影響到訓練的收斂。這裡有點類似於動態規劃與貪心演算法。這個問題在《A Stochastic Quasi-Newton Method for Online Convex Optimization》有解釋過。

最近也在看這個問題，我來拋個磚

1，Hessian矩陣的空間代價是O(n^2)，神經網路本來參數就多，儲存一個完整的Hessian矩陣相當不現實，但是事實上神經網路是可以用二階優化方法的，由於我們更多地計算Hessian矩陣H與某個向量v的乘積Hv，所以可以在不計算Hessian的情況下隱式計算Hv, 這種方法叫Pearlmutter trick, 參考https://www.researchgate.net/publication/2822332_Fast_Exact_Multiplication_by_the_Hessian，

由於向量v是可以任意的，你可以甚至取v的一些特定的值來逐行計算出神經網路的Hessian矩陣。

2，題目里這篇論文裡面就提及了一個方法來克服saddle point的問題，說了一大通為什麼傳統方法會stuck在平坦區域，然後提出了一個叫saddle free newton的方法，這個方法的思想大概是對error function進行一階近似，然後用一階和二階泰勒展開的誤差來約束住信賴域的邊界。

3，關於SGD為什麼不用做step length估計這個問題，是因為對於所有做線性搜索的優化演算法，都要求有比較準確的error function值，比如一個均方誤差的目標函數，往往是這樣：

它等於模型對於每個數據的平方誤差求和，m是所有的數據，而在SGD的每一步，它選取的只是一個，或一部分的數據，也就是上式單獨取某部分 i 的平方誤差，構造出一個單步的error function，是所有數據的error function的一個近似，我們顯然不能用這個單步的error function做line search,因為搜索出的這個單步函數在這個方向的最小值並不代表就是實際上的error function 這個方向的最小值。也因為這樣，batch SGD的步長和batch 數其實根本沒辦法確定一個最好的值，這兩個數控制了梯度有多少變異，梯度變異太大，沒辦法使我們的解停留在正確的位置，梯度變異太小，又會卡在saddle point。我的經驗是，當模型學習一個確定的映射時，sgd效果比較好，但當學習一個條件概率分布時，由於單步梯度變異太大，就會出現上面的困境。

當然可以用，實際上早期常提的trick之一就是用二階方法代替一階方法。然而你會發現沒什麼太大卵用，層數一多、訓練樣本量一大優化演算法的區別並不大，包括一階演算法本身的一些trick如momentum後來也都不太提了，簡單實用mini-batch最好用。

關於二階方法最近也有一篇

Second Order Stochastic Optimization for Machine Learning in Linear Time

https://arxiv.org/abs/1602.03943

主要的方法是用Talyor approximiation去求Hessian逆矩陣

但是作者也說將二階方法用於深度學習並沒有加快多少

? 不是不可以，看你怎麼用。

https://jimmylba.github.io/papers/nsync.pdf?

主要是複雜度，二階方法的複雜度多是平方級。對於工程用的神經網路來說，具體某個點的準確度不重要，接納並訓練儘可能多的樣本才重要。如果因為複雜度使得同樣時間下樣本數變少，實際上是緣木求魚