為什麼隨機梯度下降方法能夠收斂？

01-05

在解決大規模機器學問題的時候，通常梯度下降法因為計算開銷過大，而被隨機梯度下降法取代，每次只使用一個數據樣本來尋找梯度下降方向。一直沒有搞清隨機梯度下降法的數學原理，為什麼這種方法能夠收斂。

能夠收斂的原因無非就是實驗中確實收斂。

此外，就是SGD演算法的收斂性有理論保證，確切的說是能夠在一定條件下次線性收斂。

通俗易懂的收斂性質分析參考文獻有：

ROBUST STOCHASTIC APPROXIMATION APPROACH TO
STOCHASTIC PROGRAMMING

http://www.eecs.berkeley.edu/~brecht/cs294docs/week1/09.Nemirovski.pdf

首先要說明，隨機梯度法在凸函數的假設下是有嚴格的收斂性證明的。之前的答案僅僅從直覺上解釋我覺得還不夠。

關於原因，我覺得大概有兩點：

1.隨機梯度的期望是梯度本身，而隨機梯度法的收斂性分析也多數是在期望意義下研究的。

2.隨機梯度下降為了確保收斂，相比於同等條件下的梯度下降，需要採用更小的步長和更多的迭代輪數。

第一點比較顯然不多解釋。

第二點是上面的答主們沒有提到的。以目標函數強凸+光滑為例。為了達到 $varepsilon$ 的精度，梯度下降用 $O(1)$ 的學習率就可以確保收斂，而隨機梯度需要用 $O(t^{-1})$ (t為迭代輪數)的學習率才能收斂。這個區別帶來的後果是前者只要 $O(log(varepsilon^{-1}))$ 輪即可收斂，而後者需要 $O(varepsilon^{-1})$ 輪才可以。在一些較弱的假設下也有類似結果。

參考：

Y. Nesterov, Introductory Lectures on Convex Programming

A. Rakhlin, O. Shamir, K. Sridharan, Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization

可以參考這一篇，隨機梯度下降。

別人寫的。

兩圖預警！

真的想知道為什麼收斂，怎麼收斂，和收斂到什麼，去讀論文。。

推薦一個綜述，arxiv.org 的頁面 Optimization Methods for Large-Scale Machine Learning，第四章，Analyses of Stochastic Gradient Methods.

然後這裡兩張圖（過度簡化，原型來自Convex Optimization Algorithms）用來解釋直觀上為什麼隨機梯度下降方法

1. 便宜（cheap...）

2. 『可以』收斂（在這個例子里收斂到極小）

3. 步長很重要

4. batch很重要

5. tricks/tips很重要

這裡只談方法，應用樓上大神都說了。

第一張圖七條曲線，六條較細的都是些簡單的極小值為0的一維凸函數，中間那個紅色加粗的曲線是所有這些函數的和函數（為了更好看，我把和函數向下平移到了使其極小值為0的位置，函數性質不變）

假設初始點是-4，目標就是找個迭代演算法找到使和函數（紅色加粗曲線）達到極小值的那個點（0.8附近），這裡只考慮基於梯度的一階方法。

1. 如果使用隨機梯度下降法，每次迭代會隨機選擇六個函數中的一個算其梯度確定該函數的下降方向，然後選擇步長開始迭代。相比於全梯度，隨機梯度下降確定的移動方向（並不一定是和函數的下降方向）每次只需要1/6的計算量，所以便宜。

2. 從初始點-4開始，隨機選擇六個函數中的任何一個，所產生的梯度方向都是向右的，都是指向和函數的極小點的。持續迭代，如果當前迭代點離極小點很遠，就會以大概率得到指向和函數極小點的方向。如果步長選擇『得當』，就『可以』『收斂』。

3. 為什麼步長很重要，如果當前迭代點離和函數極小點很遠，會有較大的概率得到正確的下降方向，這時候選擇大的步長，可以加快收斂速度。但是如果當前迭代點離和函數很近，就會以相近的概率得到正確或者錯誤的下降方向，如果步長依然較大，就會產生振蕩，在極小點附近來回跳動。

4. 為什麼batch很重要，看第二個圖，這裡我分別對前兩個，中間兩個，後面兩個函數（也可以用其它的組合方式）求和得到三個新的凸函數（同樣做了平移處理），也就是選擇batch size等於2。這樣三個函數的和函數依舊是那個紅色加粗曲線。同上分析，每一次迭代，相比計算全梯度只需要1/3的計算量，相對便宜。另一方面，在和函數極小點附近，振蕩的劇烈程度會變小，因為選擇變少，更stable。

5. 那貌似可以把batch取成6，就是使用全梯度，每次都有確定的下降方向，最stable。這就是梯度下降法，用線性搜索也會有確定性的收斂理論。但是當n很大（Empirical risk minimization），各個函數不凸（神經網路）的時候，計算全梯度和用線性搜索需要巨大的運算量，如果不用線性搜索就會需要很小的步長，實際中收斂會非常慢。

所以對這類大規模問題幾乎必須要選擇隨機梯度演算法，那怎麼選擇合適的步長，怎麼選擇batch，是不是可以對不同的batch選擇不同的步長，如何加速？這個博客可以幫忙理解An overview of gradient descent optimization algorithms 小哥前幾天把這個博客的內容加了點料整理成了一篇論文arxiv.org 的頁面。。閃瞎並膜拜著。

直觀只用於感受，如果真要理解，請移步回答開始給出的綜述。。

O 了。

這個叫依概率收斂吧

我先給個通俗易懂但不太靠譜的解釋.....

如果一個模型使用於所有點，理論上也適用於這其中的1000個點（training set），也就適用於1000個點中隨機的100個點。

所以每次從1000個點中隨機抽出的100個點也就大致反映了這1000個點得性質，所求得的cost function也是大致一致的。所以1000個點收斂，100個點也會收斂...但是關鍵是learning rate

呃多謝評論提醒我概念不清 上面是mini-batch gradient descent.。SGD應該是每次只取一個樣本

那麼更嚴謹的答案在這裡

https://hal.archives-ouvertes.fr/file/index/docid/359142/filename/ASCONVEXSET.BASIC.IJPAM.1.pdf

sgd為什麼work看上面期望收斂證明.順送感性筆記。

首先sgd vs batch

sgd的特點：noise 和避免重複的pattern反覆出現.

noise的好處：避免進入局部最優，可以尋找更多的局部最優，整體變好的概率大.

減少重複pattern的好處：避免重複計算，收斂速度快。

而且，可以觀測到模型的變化。

batch的好處是：

1.理解簡單，計算簡單

2.有些learning必須batch,比如共軛梯度

3.learn rate等更好確定.

4.方便二階優化

sgd的壞處，有時候模型到接近局部最優時候波動大，

一般可以通過通過adaptive learn rate(r/t,r是初始lr,t是已出現pattern數量)來確定,

也可以使用minibatch來增加一個batch中pattern的數量，通過adaptive batch size，從小到大.

在實際系統中，由於sgd除了穩定性外，還反覆更新參數，網路佔用大，所以用minibatch也可以減小網路傳輸.
所以在實際系統中，可以固定minibatch size而採用adaptive learn rate,也可以採用固定learn rate,採用adaptive batch size同時小心的adapt learn rate或者固定.

其實也可以這麼理解，但前提是你已經接受了這個假定：（batch）梯度下降是收斂的，下面來看看(batch)梯度下降和所謂的SGD有什麼關聯。

假設我們有一批訓練數據 $D = {(x_1, y_1), ..., (x_N, y_N)}$ , 而這些訓練數據是從一個未知的真實的分布 $p(x)$ 產生出來的 ( $x_i sim p(x) ~~ i in {1,...,N}$ )。假設模型的參數為 $mathbf{W}$

在整個優化過程里，準確地講，我們需要去優化的是Expected loss，也就是從 $p(x)$ 產生出來的所有的樣本。

可以寫成:

$L(W) = E_x[L(W,x)]=int p(x)L(W,x)dx$ (對於所有可能的樣本x, 計算expected loss，這才是理想情況下真正需要去minimize的損失函數！)

那相對應的梯度為：

$riangledown_W L(W) = riangledown_W E_x[L(W,x)]=E_x[ riangledown_W L(W,x)]$

從而可以得到梯度下降法的更新函數：

$W^{t+1} = W^t - eta E_x[ riangledown_W L(W,x)]$

然而，後面的expected loss很難計算，因為我們其實不知道背後的真實的分布 $p(x)$ 。這種情況下，第一個想到的方法就是用蒙特卡洛（monte carlo）演算法做近似估計(approximation). 可以寫成：

$E_x[ riangledown_W L(W,x)] approx hat{ riangledown} L(W) = frac{1}{M}sum_{i=1}^{M}L(W,x_i)$ (近似部分由蒙特卡洛演算法得到)

由蒙特卡洛演算法的特點，隨著M值的增大，我們的估計會更準確。

好了，最後可以總結為：

- M 等於 N時（就是用了所有的樣本），就是所謂的batch GD

- M 等於 1時（就是用了其中的一個樣本），就是所謂的SGD

- M 大於1，小於 N時，就是 mini-batch GD.

所以從expected loss的角度看，其實batch GD, mini-batch GD, SGD都可以看成SGD的範疇，只不過區別在於每次取多少的樣本了。

批梯度下降使用所有點的殘差平方和(記殘差平方和的平均數為J1)，隨機梯度下降使用某點的殘差平方(記為J2)。

理論上，訓練集的所有點都在擬合函數hθ(x)附近呈高斯分布。那可以認為J2-J1的值呈高斯分布~N(0,σ^2)，或者說J2在J1附近高斯分布，也就是差不多的意思。

既然關於θi，大家的值都差不多那還不如每次只挑1個來算一下J(θ)，反正就算個方向嘛，方向不准沒關係，多走幾步嘛，不走反就好了，也能提到對擬合值準確度估計的作用。

這一隨機，省下了m倍的計算量，步子只是多邁了一點點，非常划得來。

在模型的訓練過程之中，我們的理想目標是獲取全局最優點，但是如果代價函數是非凸的，那麼，我們所能獲取的就只能是局部最優。因為不知道你的代價函數是什麼，所以，不確定能否收斂到全局最優，值得指出的，大部分情況下，代價函數都是非凸的，只有局部最優值。

那麼，我們接下來聊一聊如何收斂到局部最優。模型的訓練本質上是模型參數值的確定。在局部最優的時候，參數的表現是基本穩定下來，不再發生任何變化。如果你在訓練模型的過程之中進行參數可視化的話，你會發現參數要經過很多輪迭代才能穩定下來，這意味著如果使用的訓練數據比較少的話，是有可能達不到局部最優值的，但是它會一直在靠近。那麼，問題來了，既然使用的數據少（隨機梯度下降法就用的數據少）可能無法找到局部最優值，為什麼還要使用它呢？因為在很大概率上，它確實是能夠靠近的，又不用那麼大的計算量，所以就被廣泛使用了。

還是乖乖去看正兒八經的論文吧，在這兒問，然後看各路大神的回答，不小心就會變成民科的，就像桃谷六仙給令狐沖輸送內力一樣，只會適得其反

期望收斂而已