梯度下降算法綜述！
背景介紹
圖1：梯度下降算法示意圖
隨著近年來(lái)深度學(xué)習(xí)領(lǐng)域的蓬勃興起，梯度類(lèi)算法成為了優(yōu)化神經(jīng)網(wǎng)絡(luò)的最重要的方法。各種深度學(xué)習(xí)的框架(如Caffe, Keras, TensorFlow and PyTorch)中，均支持各種各樣的梯度類(lèi)優(yōu)化器。梯度類(lèi)方法在深度學(xué)習(xí)中如此重要的主要原因是深度神經(jīng)網(wǎng)絡(luò)中數(shù)以百萬(wàn)、千萬(wàn)級(jí)別的待優(yōu)化參數(shù)使得諸如牛頓法和擬牛頓法等高階優(yōu)化方法不再可行，而梯度類(lèi)方法借助GPU計(jì)算資源的支持可以進(jìn)行高效的運(yùn)算。然而天下沒(méi)有免費(fèi)的午餐，當(dāng)我們使用一階優(yōu)化算法獲取其計(jì)算可行性上的好處時(shí)，付出的代價(jià)便是一階算法較慢的收斂速率。尤其是當(dāng)目標(biāo)函數(shù)接近病態(tài)系統(tǒng)時(shí)，梯度類(lèi)算法的收斂速度會(huì)變得更加緩慢。除此之外，由于深度神經(jīng)網(wǎng)絡(luò)的損失函數(shù)極其復(fù)雜且非凸，梯度類(lèi)算法優(yōu)化得到的模型參數(shù)的性質(zhì)未知，依賴(lài)于算法的參數(shù)選取和初值的選取。因此，目前深度學(xué)習(xí)中的梯度類(lèi)算法實(shí)際上是某種意義上的黑箱算法，其可解釋性仍然面臨著巨大挑戰(zhàn)。
梯度下降算法的變體
批量梯度下降
隨機(jī)梯度下降
小批量梯度下降
圖2：三種梯度下降算法的對(duì)比示意圖
梯度下降算法的改進(jìn)算法
如前所說(shuō)，梯度下降算法作為一階算法有其固有的局限性，僅僅使用損失函數(shù)的一階信息進(jìn)行更新是比較“短視”的做法，在病態(tài)系統(tǒng)下收斂速度極為緩慢。學(xué)者們也提出了一系列方法來(lái)加速梯度下降算法，主要的思路是對(duì)梯度下降法的兩個(gè)主要組成部分進(jìn)行修改，即更新方向和學(xué)習(xí)率。我們接下來(lái)主要介紹其中幾種十分重要的算法。請(qǐng)注意，以下算法原始版本均是在非隨機(jī)優(yōu)化或BGD的條件下討論的，但是在實(shí)際深度學(xué)習(xí)的應(yīng)用中往往是使用了MGD的版本，我們?cè)谙挛牡慕榻B中并不區(qū)分這些細(xì)節(jié)。
動(dòng)量梯度下降
動(dòng)量梯度下降(Gradient Descent with Momentum)法 [Polyak, 1964, Ning, 1999]，也被稱(chēng)為重球(Heavy Ball, HB)方法，是對(duì)梯度下降算法的經(jīng)典改進(jìn)算法，其更新公式如下：
Nesterov動(dòng)量梯度
Nesterov動(dòng)量梯度(Nesterov accelerated gradient, NAG)方法 [Nesterov, 1983]，是動(dòng)量梯度下降法的改進(jìn)版本，其更新公式如下：
圖3：動(dòng)量梯度下降與NAG的對(duì)比示意圖
AdaGrad
AdaDelta
RMSprop
RMSprop[Tieleman and Hinton, 2012]和AdaDelta的思路十分相似，兩個(gè)算法同年分別被Hinton和Zeiler提出，有趣的是Hinton正是Zeiler的導(dǎo)師。RMSprop最早出現(xiàn)在Hinton在Coursera的課程中，這一算法成果并未發(fā)表。其更新公式與第一階段的AdaDelta一致：
Adam
自適應(yīng)矩估計(jì)算法(Adaptive Moment Estimation, Adam)[Kingma and Ba, 2015]是將搜索方向和學(xué)習(xí)率結(jié)合在一起考慮的改進(jìn)算法，其原論文引用量為ICLR官方引用最高的文章。Adam的思路非常清晰：搜索方向上，借鑒動(dòng)量梯度下降法使用梯度的指數(shù)加權(quán)；學(xué)習(xí)率上，借鑒RMSprop使用自適應(yīng)學(xué)習(xí)率調(diào)整。所謂矩估計(jì)，則是修正采用指數(shù)加權(quán)帶來(lái)的偏差。其更新公式具體如下：
AdaMax 與 Nadam
Nadam[Dozat, 2016]則是將Adam中關(guān)于搜索方向的部分改為使用Nesterov動(dòng)量。在引入其更新公式之前，我們首先給出NAG的等價(jià)更新形式。
一些可視化結(jié)果
我們展示兩幅圖片來(lái)對(duì)比不同的優(yōu)化算法的表現(xiàn)，如圖4所示。
圖4：梯度下降算法的可視化結(jié)果
圖4-(a)展示的是六種梯度下降改進(jìn)算法在Beale函數(shù)的函數(shù)曲面的優(yōu)化路徑。等高線(xiàn)由紅變藍(lán)的過(guò)程表示函數(shù)值由大到小，最小值點(diǎn)在圖中由五角星標(biāo)出。所有的算法均從同一點(diǎn)出發(fā)，可以看到自適應(yīng)學(xué)習(xí)率類(lèi)的算法(AdaGrad, AdaDelta和RMSprop)的優(yōu)化路徑直接走向了右邊的極小值點(diǎn)，但是動(dòng)量梯度法(綠色曲線(xiàn))和NAG(紫色曲線(xiàn))均是先走到了另一處狹長(zhǎng)的區(qū)域，再轉(zhuǎn)向極小值點(diǎn)，且NAG的糾正速度快于動(dòng)量梯度法。
圖4-(b)展示的是六種梯度下降改進(jìn)算法在鞍點(diǎn)附近的優(yōu)化路徑。所謂鞍點(diǎn)就是，滿(mǎn)足一階條件等于0但是海森矩陣的特征值有正有負(fù)的點(diǎn)。由于梯度下降算法僅僅考慮一階條件，理論上會(huì)受到鞍點(diǎn)的困擾。可以看到，SGD(紅色曲線(xiàn))在鞍點(diǎn)處停止，動(dòng)量梯度法(綠色曲線(xiàn))和NAG(紫色曲線(xiàn))在鞍點(diǎn)處停留一會(huì)后逐漸脫離鞍點(diǎn)，而三種自適應(yīng)學(xué)習(xí)率算法則能夠快速擺脫鞍點(diǎn)。
梯度類(lèi)算法相關(guān)研究
并行SGD和分布式SGD
在當(dāng)今無(wú)處不在的大數(shù)據(jù)時(shí)代，數(shù)據(jù)的分布方式和使用方式都不再像原來(lái)一樣單一。與之對(duì)應(yīng)的，當(dāng)數(shù)據(jù)仍然保存在本地，學(xué)者們開(kāi)始研究如何在單機(jī)上實(shí)現(xiàn)并行SGD[Niu et al., 2011]來(lái)進(jìn)行加速；當(dāng)數(shù)據(jù)分散地保存在不同的節(jié)點(diǎn)，如何實(shí)現(xiàn)分布式SGD[Jeffrey Dean and Ng., 2012, Mcmahan and Streeter, 2014, Sixin Zhang and LeCun, 2015]；更進(jìn)一步地，對(duì)于數(shù)據(jù)節(jié)點(diǎn)十分龐大而又需要保護(hù)用戶(hù)隱私的時(shí)代，聯(lián)邦學(xué)習(xí)(Federated Learning)版本的SGD[H. Brendan McMahan and y Arcas, 2016]同樣也是學(xué)者們關(guān)注的問(wèn)題。由于篇幅原因，我們不在這里進(jìn)行展開(kāi)。
梯度類(lèi)算法的訓(xùn)練策略
除了算法層面的改進(jìn)，與算法相配套的訓(xùn)練策略或者其他技術(shù)同樣對(duì)訓(xùn)練模型有很大的影響。例如：
數(shù)據(jù)打亂和課程式學(xué)習(xí). 有學(xué)者指出避免讓數(shù)據(jù)以固定單一的方式進(jìn)入模型訓(xùn)練能夠提升模型的泛化能力，因此在深度學(xué)習(xí)模型的訓(xùn)練中人們?cè)诿恳淮伪闅v全樣本后都會(huì)進(jìn)行數(shù)據(jù)打亂(Shuffling)。另一方面，有學(xué)者指出讓數(shù)據(jù)以某種有意義的順序參與模型訓(xùn)練能夠使模型更快收斂且表現(xiàn)不錯(cuò)，這樣的方法被稱(chēng)為課程式學(xué)習(xí)(Curriculum Learning)[Yoshua Bengio and Weston, 2009]. 批量歸一化. 批量歸一化(Batch normalization)[Ioffe and Szegedy, 2015]是卷積神經(jīng)網(wǎng)絡(luò)中經(jīng)常使用的技術(shù)，它能夠?qū)γ總€(gè)小批量的數(shù)據(jù)在模型的某些節(jié)點(diǎn)進(jìn)行歸一化。大量實(shí)驗(yàn)表明，這種技術(shù)能夠加速梯度類(lèi)算法的收斂、讓梯度類(lèi)算法使用更大的初始學(xué)習(xí)率以及減少參數(shù)初始化的影響。 早停. 通過(guò)監(jiān)控驗(yàn)證集的精度指標(biāo)來(lái)決定是否要提前終止算法訓(xùn)練。 梯度噪聲. [Neelakantan et al., 2015]提出在梯度上增加獨(dú)立的高斯噪聲，來(lái)幫助梯度類(lèi)算法增加穩(wěn)健性。他們猜測(cè)，增加的梯度噪聲能夠幫助算法跳過(guò)局部鞍點(diǎn)和次優(yōu)的極小值點(diǎn)。
梯度類(lèi)算法仍然面臨的挑戰(zhàn)
盡管我們已經(jīng)介紹了非常多的梯度類(lèi)算法的改進(jìn)算法，但是梯度類(lèi)算法仍然面臨著許多挑戰(zhàn)。
選擇合適的學(xué)習(xí)率是非常困難的事情。盡管在傳統(tǒng)的優(yōu)化領(lǐng)域和我們之前提到的自適應(yīng)學(xué)習(xí)率算法提供了很多解決這個(gè)問(wèn)題的方法。在深度模型的訓(xùn)練中，這些已有的方法仍然會(huì)遇到問(wèn)題，因此這仍是一個(gè)需要小心考慮和諸多嘗試的問(wèn)題。 盡管梯度下降算法在理論上有許多性質(zhì)和結(jié)論，但實(shí)際得到神經(jīng)網(wǎng)絡(luò)往往不滿(mǎn)足已有結(jié)論的前提假設(shè)。在我們優(yōu)化超高維非凸的損失函數(shù)時(shí)，如何保證算法不被鞍點(diǎn) [Zeiler, 2014]、平坦區(qū)域所困擾，依然是十分挑戰(zhàn)的問(wèn)題。 對(duì)于超高維得到損失函數(shù)，梯度類(lèi)算法表現(xiàn)地像黑箱優(yōu)化器，目前上沒(méi)有特別好的方法對(duì)這種超高維優(yōu)化進(jìn)行可視化分析。
參考文獻(xiàn)
Augustin-Louis Cauchy. Mode grale pour la rlution des systs d’ations simultan. Comptes rendus des sces de l’ Acade des sciences de Paris, pages 536–538, 10 1847.
Xi Chen, Jason D Lee, Xin T Tong, and Yichen Zhang. Statistical inference for model parameters in stochastic gradient descent. arXiv preprint arXiv:1610.08637, 2016.
Haskell B. Curry. The method of steepest descent for non-linear minimization problems. Quarterly of Applied Mathematics, pages 258–261, 2 1944.
Jia Deng, Wei Dong, Richard Socher, Li Jia Li, and Fei Fei Li. Imagenet: A large-scale hierarchical image database. In IEEE Conference on Computer Vision and Pattern Recognition, 2009.
Timothy Dozat. Incorporating nesterov momentum into adam. ICLR Workshop, 2016.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(7):257–269, 2011.
Igor Gitman, Hunter Lang, Pengchuan Zhang, and Lin Xiao. Understanding the role of momentum in stochastic gradient methods. In Proceedings of 33rd Conference and Workshop on Neural Information Processing Systems, 2019.
Daniel Ramage Seth Hampson H. Brendan McMahan, Eider Moore and Blaise Aguera y Arcas. Communication-efficient learning of deep networks from decentralized data. In International Conference on Machine Learning (ICML), 2016.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Proceedings of the 32nd annual international conference on machine learning, 2015.
Rajat Monga Kai Chen Matthieu Devin Quoc V. Le Mark Z. Mao Marc Aurelio Ranzato Andrew Senior Paul Tucker Ke Yang Jeffrey Dean, Greg S. Corrado and Andrew Y. Ng. Large scale distributed deep networks. In Neural Information Processing Systems Conference (NIPS 2012), pages 1–11, 2012.
Diederik P. Kingma and Jimmy Lei Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, pages 1–13, 2015.
H. Brendan Mcmahan and Matthew Streeter. Delay-tolerant algorithms for asynchronous distributed online learning. In Neural Information Processing Systems Conference (NIPS 2014), pages 1–9, 2014.
A. Neelakantan, L. Vilnis, Q. V. Le, I. Sutskever, and J. Martens. Adding gradient noise improves learning for very deep networks. arXiv preprint arXiv:1511.06807., 2015.
Arkadii S. Nemirovski, Anatoli Juditsky, Guanghui Lan, Shapiro, and A. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4):1574–1609, 2009.
Y. E. Nesterov. A method for solving the convex programming problem with convergence rate o(1/ ). Dok- l.akad.nauk Sssr, 269, 1983.
Q. Ning. On the momentum term in gradient descent learning algorithms. Neural Netw, 12(1):145–151, 1999.
F. Niu, B. Recht, C. Re, and S. J. Wright. Hogwild!: A lock-free approach to parallelizing stochastic gradient descent. In Neural Information Processing Systems Conference (NIPS 2011), pages 1–22, 2011.
B. T. Polyak. Some methods of speeding up the convergence of iteration methods. Ussr Computational Mathe- matics Mathematical Physics, 4(5):1–17, 1964.
A. Rakhlin, O. Shamir, and K. Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. In International Conference on Machine Learning, 2012.
Anna Choromanska Sixin Zhang and Yann LeCun. Deep learning with elastic averaging sgd. In Neural Information Processing Systems Conference (NIPS 2015), pages 1–9, 2015.
R.S. Sutton. Twoproblemswith backpropagationand other steepest-descent learning proceduresfor networks. proc cognitive sci soc, 1986.
T. Tieleman and G. Hinton. Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural Networks for Machine Learning, pages 26–31, 2012.
Panos Toulis and Edoardo M. Airoldi. Asymptotic and finite-sample properties of estimators based on stochastic gradients. Eprint Arxiv, 45(4):1694–1727, 2017.
Ronan Collobert Yoshua Bengio, Jme Louradour and Jason Weston. Curriculum learning. In Proceedings of the 26th annual international conference on machine learning, pages 41–48, 2009.
Matthew D. Zeiler. Adadelta: An adaptive learning rate method. arXiv preprint arXiv:1212.5701, 2012.
Matthew D. Zeiler. Identifying and attacking the saddle point problem in high-dimensional nonconvex optimization. arXiv preprint arXiv:1406.2572, 2014.
- END -