梯度下降法的搜索方向顧名思義就是梯度方向，也就是當(dāng)前點(diǎn)所在地形最陡峭的下降方向（你這個圖里面只有左右兩個方向）予跌。
步長的選擇要看函數(shù)的性質(zhì)搏色，一般可導(dǎo)函數(shù)，只要步長足夠小券册，則保證每次函數(shù)值都不會增加频轿，此外：
1. 如果函數(shù)可導(dǎo)，且函數(shù)的梯度滿足李普希茲連續(xù)(常數(shù)為L)烁焙，若以小于（1/L）的步長迭代航邢，則能保證每次迭代的函數(shù)值都不增，則保證最終會收斂到梯度為0的點(diǎn)骄蝇。也可以采用Line search確定步長膳殷，Line search的本質(zhì)目的其實也是為了保證函數(shù)值下降(或稱作不增)。
2. 如果函數(shù)還是凸的九火，則最終會走到最優(yōu)點(diǎn)赚窃。
作者：li Eta
來源：知乎
鏈接：https://www.zhihu.com/question/37911687/answer/74529437
對于full gradient方法，一般都是line search岔激，基本思想就是每次試一個步長勒极，如果用該步長走的話，看函數(shù)值會不會比當(dāng)前點(diǎn)下降一定的程度虑鼎，如果沒有辱匿，就按比例減小步長冀惭，再試，直到滿足條件（根據(jù)泰勒展開式我們知道步長足夠小時總會滿足下降條件）掀鹅。所以line search實際上是計算量比較大的散休，不過在以前數(shù)據(jù)量不大的情況下這都不是問題。關(guān)于line search乐尊，我覺得[1]寫的極好戚丸。
此外，還有一種方法叫Barzilai-Borwen方法（簡稱BB扔嵌，[2]）限府，這種方法源自擬牛頓法，非常簡單痢缎，基本不用額外計算也可以很好的估計步長胁勺。這個方法缺點(diǎn)就是，有可能不收斂独旷，所以一般的用法是先用BB算一個步長署穗、再從這個步長出發(fā)用line search，這樣可以大大減少line search的次數(shù)嵌洼。關(guān)于BB法可以推薦看綜述[3]案疲。
對于SGD，普通的line search計算量太大根本不可能麻养。目前沒有非常成熟的辦法褐啡，實際中還是靠手動調(diào)步長。當(dāng)然鳖昌，最近幾年也有一些工作：
最有名的是AdaGrad和改進(jìn)版的AdaDelta备畦，這兩個方法有用，至少可以確保收斂许昨，但速度上不夠好懂盐，遠(yuǎn)不如手動調(diào)的最好步長，特別迭代次數(shù)多了之后车要。當(dāng)然他們的優(yōu)點(diǎn)就是在不怎么要手動調(diào)參允粤、基本不用額外計算量的情況下收斂的還可以。
[4] 中有提出過一種簡化版line search方法翼岁。這種方法每輪迭代只用一個子函數(shù)做一次line search來估計Lipschitz常數(shù)L，然后選擇理論上最好的步長司光，比如說1/L琅坡，這樣相對計算量還可以接受了。但這個方法有兩個問題：一是只能用在SAG残家、SVRG這種固定步長能保證收斂的算法上榆俺，原始的SGD不行；第二就是，就算知道了L茴晋，但實際中最佳步長和理論最佳往往差了很遠(yuǎn)陪捷。但總的來說，根據(jù)我實驗觀察诺擅，這是種比較靠譜的方法市袖。
[5] 提出了一種probabilistic line search∷赣浚基本思想就是在每個迭代點(diǎn)計算一個子函數(shù)的值苍碟，然后用Gaussian Process來做擬合，給出目標(biāo)函數(shù)在每個的估計值撮执，然后利用這個估計值來做line search微峰。我自己沒有親自實驗過這種方法，但個人感覺就是計算量仍然偏大（除了每次迭代要計算一個函數(shù)值抒钱，還要要不斷計算和更新一個Gaussian process）蜓肆，而且感覺不一定能收斂。
[6] 是做SGD步長估計的谋币，幾個月前才出爐的paper症杏。大概思想是假設(shè)步長服從某個簡單的函數(shù)，比如
（因為SGD需要diminishing的步長來保證收斂）瑞信，這兒k是指第幾輪迭代厉颤，C是某個我們要估計的常數(shù)。然后在每輪迭代的時候用online梯度下降的方法更新下對C的估計凡简。但是這篇paper實驗做的巨簡單無比逼友，不太清楚這個方法到底咋樣。最后秤涩，我最近有篇paper關(guān)于這個問題帜乞，等發(fā)了再說。
參考文獻(xiàn)：
[1] Nocedal, Jorge, and Stephen Wright.Numerical optimization. Springer Science & Business Media, 2006.
[2] Fletcher, R. (2005). On the barzilai-borwein method. InOptimization and control with applications(pp. 235-256). Springer US.
[3] Raydan, Marcos. "On the Barzilai and Borwein choice of steplength for the gradient method."IMA Journal of Numerical Analysis13.3 (1993): 321-326.
[4] Roux, Nicolas L., Mark Schmidt, and Francis R. Bach. "A stochastic gradient method with an exponential convergence _rate for finite training sets."Advances in Neural Information Processing Systems. 2012.
[5] Mahsereci, Maren, and Philipp Hennig. "Probabilistic line searches for stochastic optimization."Advances In Neural Information Processing Systems. 2015.
[6] Massé, Pierre-Yves, and Yann Ollivier. "Speed learning on the fly."arXiv preprint arXiv:1511.02540(2015).
作者：Martin Tan
鏈接：https://www.zhihu.com/question/37911687/answer/93944721
來源：知乎
