[論文閱讀] 綜述梯度下降最佳化演算法

作者：由姚鑫發表于書法時間：2020-03-01

論文標題：《An overview of gradient descent optimization algorithms》

論文連結：

https：//

arxiv。org/pdf/1609。0474

主要講述常見的梯度下降最佳化演算法的變化過程，包括SGD、Momentum、NAG、AdaGrad、RMSProp/AdaDelta、Adam、Nadam。

1。基本框架

上述最佳化演算法均遵循以下基本框架，這是迭代過程的核心公式。

定義當前時刻待最佳化引數

$\theta_t \in R^d$

，損失函式為

$J(\theta)$

，學習率為

$\eta$

，引數更新框架為：

1。計算損失函式關於當前引數的梯度：

$g_t=\bigtriangledown J(\theta_t)$

2。根據歷史梯度計算一階動量和二階動量：

$m_t=\phi(g_1,g_2,...,g_t)$

，

$V_t=\psi(g_1,g_2,...,g_t)$

3。計算當前時刻的下降梯度：

$\Delta \theta_t=-\eta\cdot\frac{m_t}{\sqrt {V_t}}$

4。根據下降梯度更新引數：

$\theta_{t+1}=\theta_t+\Delta\theta_t$

那麼在不同的最佳化演算法中，究竟是哪裡發生了變化呢？我們接著往下看，每一個演算法都可以對照這個基本框架進行理解。

2。 SGD（Stochastic Gradient Descent）

著名的隨機梯度下降演算法，SGD中沒有闡述動量的概念，即沒有考慮歷史梯度。所以在SGD中，當前時刻的一階動量即為當前時刻的梯度

，且二階動量

，所以SGD的引數更新公式為：

$\Delta \theta_t=-\eta\cdot\frac{m_t}{\sqrt {V_t}}=-\eta\cdot\frac{g_t}{\sqrt{E}}=-\eta\cdot g_t$

$\theta_{t+1}=\theta_t+\Delta\theta_t=\theta_t-\eta\cdot g_t$

完全是按照基本框架來的！

批次梯度下降（Batch gradient descent）、隨機梯度下降（SGD）、小批次梯度下降（Mini-batch gradient descent）

其實都是一回事

，區別在於對多少樣本數量計算梯度，BGD是對所有樣本計算梯度（一次性傳入所有樣本，計算損失函式，進而計算梯度），理論上可以找到全域性最優解；SGD是對一個樣本計算梯度（一次隨機選取一個樣本進行計算），每次都是往區域性最優的方向下降；MBGD是對一個批次樣本計算梯度（一次傳入一個批次的樣本資料進行計算），依然是往區域性最優的方向下降。

當樣本量很大時，一次性讀入所有樣本顯然是不可取的。所以通常使用SGD或者說BGD，但兩者都不可避免

會發生震盪

，隨著每次傳入樣本的不同，計算得到的梯度也會不同，自然就會產生震盪。

3。 Momentum

在介紹Momentum前，先介紹一下

指數加權移動平均

（Exponentially Weighted Moving Average，EWMA）：

假設

$v_{t-1}$

是

時刻的指數加權移動平均值，

$\theta_t$

是

時刻的觀測值，那麼

時刻的指數加權平均值為：

$v_t = \beta v_{t-1}+(1-\beta)\theta_t =(1-\beta)\theta_t+\sum_{i=1}^{t-1}(1-\beta)\beta^i\theta_{t-i}$

其中

$0\leq\beta<1$

，

。顯然，由上式可知，

時刻的指數加權移動平均值其實可以看作前

時刻所有觀測值的指數加權平均值，除了第

時刻的觀測值權重為

$1-\beta$

外，其他時刻的觀測值權重為

$(1-\beta)\beta^i$

。由於通常對於那些權重小於

$\frac1e$

的觀測值可以忽略不計，所以忽略掉那些觀測值以後，上式可以看做在求指數加權

移動

平均值。

那麼哪些項的權重會小於

$\frac 1e$

呢？由於

$\lim_{n \rightarrow +\infty}{(1-\frac1n)}^n=\frac1e\approx0.3679$

若令

$n=\frac1{1-\beta}$

，則

$\lim_{n \rightarrow +\infty}{(1-\frac1n)}^n=\lim_{\beta \rightarrow 1}{(\beta)}^{\frac{1}{1-\beta}}=\frac1e\approx0.3679$

所以，當

$\beta \rightarrow 1$

時，那些

$i\geq\frac1{1-\beta}$

的

$\theta_{t-i}$

的權重

$(1-\beta)\beta^i$

一定小於

$\frac1e$

。例如當

，

$\beta=0.9$

時，

$\theta_1,\theta_2,...,\theta_9,\theta_{10}$

的權重都是小於

$\frac1e$

，因此可以忽略不計，那麼此時就相當於在求

$\theta_{11},\theta_{12},...,\theta_{19},\theta_{20}$

這最近10個時刻的加權移動平均值。所以指數移動平均值可以近似看做在求最近

$\frac1{1-\beta}$

個時刻的加權移動平均值，

$\beta$

常取

$\geq0.9$

。

但是，當

較小時，指數加權移動平均值的偏差較大，例如：設

$\theta_1=40$

，

$\beta=0.9$

，那麼

$v_1=\beta v_0 + (1-\beta)\theta_1=0.9*0+0.1*40=4$

，顯然

和

$\theta_1$

相差太大，所以通常會加上一個修正因子

$1-\beta^t$

，加入修正因子後的公式為

$v_t=\frac{\beta v_{t-1}+(1-\beta)\theta_t}{1-\beta^t}$

顯然，當

很小時，修正因子

$1-\beta^t$

會起作用，當

足夠大時

$\beta^t \rightarrow0,(1-\beta^t)\rightarrow1$

，修正因子會自動退場。

SGD with Momentum

：Momentum認為梯度下降過程可以加入

慣性

，也就是在SGD基礎上

引入一階動量

。而所謂的一階動量就是該時刻梯度的指數加權移動平均值：

$\eta\cdot m_t:=\beta\cdot m_{t-1}+\eta\cdot g_t$

其中

並

不嚴格按照

指數加權移動平均的定義採用權重

$1-\beta$

，而是

使用自定義的學習率 #FormatImgID_59#

。此時，依然

沒有采用二階動量

，所以

，則Momentum的引數更新公式為

$\Delta\theta_t=-\eta\cdot\frac{m_t}{\sqrt E}=-\eta\cdot m_t=-(\beta m_{t-1}+\eta g_t)$

$\theta_{t+1}=\theta_t-(\beta m_{t-1}+\eta g_t)$

Momentum演算法就是這樣，它依然是遵循基本框架的。該演算法的主要目的就是為了

抑制SGD的震盪

而提出的。

4。 NAG（Nesterov Accelerated Gradient）

除了利用慣性（一階動量）跳出區域性“溝壑”以外，還可以嘗試“

往前走一步

”。

想象一下，你走到一個盆地，四周都是略高的小山，你覺得沒有下坡的方向，那就只能待在原地了。可是如果你爬上高地，就會發現外面的世界還很廣闊。因此，我們不能停留在當前位置去觀察未來的方向，而要“

向前多看一步

”。

在Momentum中，

時刻的主要下降方向是由歷史梯度（慣性/一階動量）決定的，當前時刻的梯度權重較小，那不如先看看如果跟著慣性走了一步，那個時候“外面的世界”是怎麼樣的。也即在Momentum的基礎上將當前時刻的梯度

換成下一時刻的梯度

$\bigtriangledown J(\theta_t-\beta m_{t-1})$

，此時仍然沒有使用二階動量，所以

，NAG的引數更新公式為：

$\Delta \theta_t=-\eta\cdot \frac{m_t}{\sqrt E}=-\eta\cdot m_t=-(\beta m_{t-1}+\eta\bigtriangledown J(\theta_t-\beta m_{t-1}))$

$\theta_{t+1} = \theta_t-(\beta m_{t-1}+\eta\bigtriangledown J(\theta_t-\beta m_{t-1}))$

將NAG於Momentum對照起來，就能看出其中的不同點，以及NAG的核心思想。

5。 AdaGrad

此前，均沒有使用二階動量。二階動量的出現，才意味著“

自適應學習率

”最佳化演算法時代的到來。SGD及其變種均以同樣的學習率更新每個緯度的引數，但深度神經網路往往包含大量的引數，這些引數並不是總會用得到。對於經常更新的引數，我們已經積累了大量關於它的只是，不希望受到單個樣本太大的影響，希望學習速率慢一些；對於偶爾更新的引數，我們瞭解的資訊太少，希望能從每個偶然出現的樣本身上多學一些，即學習速率大一些。因此，AdaGrad誕生了，它就是考慮了對不同維度的引數採用不同的學習率。

具體地，對於那些更新幅度很大的引數，通常歷史累計梯度的

平方和

會很大；相反地，對於那些更新幅度很小的引數，通常其歷史累計梯度的

平方和

會很小。所以在固定學習率的基礎上除以歷史累計梯度的平方和就能使得那些更新幅度很大的引數的學習率變小，同樣也能使得那些更新幅度很小的引數學習率變大。

所以，AdaGrad的引數更新公式為

$v_{t,i} = \sum_{t=1}^t g_{t,i}^2$

$\Delta\theta_{t,i}=-\frac {\eta}{\sqrt{v_{t,i}+\epsilon}}g_{t,i}$

$\theta_{t+1,i}=\theta_{t,i}-\frac{\eta}{\sqrt{v_{t,i}+\epsilon}}g_{t,i}$

其中

$g_{t,i}^2$

表示第

時刻第

緯度參的梯度值的平方，

$\epsilon$

是防止分母等於0的平滑項（常取一個很小的值

）。顯然，上式中的

$\frac{\eta}{\sqrt{v_{t,i}+\epsilon}}$

這個整體可以看做是學習率，分母中的歷史累計梯度值

$v_{t,i}$

越大的引數學習率越小。

上式僅僅是第

時刻第

緯度引數的更新公式，對於第

時刻所有緯度引數的整體更新公式為：

$V_t=diag(v_{t,i},v_{t,2},...,v_{t,d}) \in R^{d\times d}$

$\Delta \theta_t=-\frac{\eta}{\sqrt{V_t + \epsilon}}\cdot g_t$

$\theta_{t+1} = \theta_t-\frac{\eta}{\sqrt{V_t + \epsilon}}\cdot g_t$

注意，由於

是對角矩陣，所以

$\epsilon$

只用來平滑

對角線上的元素。

缺點：隨著迭代的進行，歷史累計梯度平方和

$v_{t,i}$

會越來越大，這樣會使得所有緯度引數的學習率都不斷減小（甚至導致梯度消失），無論更新幅度如何。

6。 RMSProp/AdaDelta

由於AdaGrad單調遞減的學習率變化過於激進，我們考慮一個改變二階動量計算方法的策略：不累計全部歷史梯度，而只關注過去一段時間視窗的下降梯度，採用Momentum中的指數加權移動平均的思想。這也就是AdaDelta名稱中Delta的來歷。

先看最簡單直接版的RMSProp，RMSProp就是在AdaGrad的基礎上將普通的歷史累計梯度平方和換成歷史累計梯度平方和的指數加權移動平均值，所以只需將AdaGrad中

$v_{t,i}$

的公式改成指數加權移動平均的形式即可，也即：

$v_{t,i}=\beta v_{t-1,i} + (1-\beta)g_{t,i}^2$

$V_t=diag(v_{t,i},v_{t,2},...,v_{t,d}) \in R^{d\times d}$

$\Delta \theta_t=-\frac{\eta}{\sqrt{V_t + \epsilon}}\cdot g_t$

$\theta_{t+1} = \theta_t-\frac{\eta}{\sqrt{V_t + \epsilon}}\cdot g_t$

而AdaDelta除了對二階動量計算指數加權移動平均以外，還對當前時刻的下降梯度

$\Delta \theta_t$

的

平方

也計算一次指數加權移動平均，具體地：

$E[\Delta \theta^2]_{t,i} = \gamma E[\Delta \theta^2]_{t-1,i} + (1-\gamma)\Delta\theta_{t,i}^2$

由於

$\Delta \theta_{t,i}^2$

目前是未知的，所以只能用

時刻的指數加權移動平均來近似替換，也即

$E[\Delta \theta^2]_{t-1,i} = \gamma E[\Delta \theta^2]_{t-2,i} + (1-\gamma)\Delta\theta_{t-1,i}^2$

除了計算出

時刻的指數加權移動平均以外，AdaDelta還用此值替換預先設定的學習率

$\eta$

。

因此，AdaDelta的引數更新公式為：

$v_{t,i}=\beta v_{t-1,i} + (1-\beta)g_{t,i}^2$

$V_t=diag(v_{t,i},v_{t,2},...,v_{t,d}) \in R^{d\times d}$

$E[\Delta \theta^2]_{t-1,i} = \gamma E[\Delta \theta^2]_{t-2,i} + (1-\gamma)\Delta\theta_{t-1,i}^2$

$\Theta_t=diag(E[\Delta\theta^2]_{t-1,1},E[\Delta\theta^2]_{t-1,2},...,E[\Delta\theta^2]_{t-1,d})\in R^{d\times d}$

$\Delta \theta_t=-\frac{\sqrt{\Theta_t+\epsilon}}{\sqrt{V_t + \epsilon}}\cdot g_t$

$\theta_{t+1} = \theta_t-\frac{\sqrt{\Theta_t+\epsilon}}{\sqrt{V_t + \epsilon}}\cdot g_t$

顯然，對於AdaDelta演算法來說，已經不需要自己預設學習率

$\eta$

了，只需要預設

$\beta$

和

$\gamma$

這兩個指數加權移動平均值的衰減率即可。

7。 Adam

講到這裡，Adam和Nadam的出現就很自然而然了——它們是前述方法的集大成者。

回顧上面內容，Momentum在SGD基礎上加了一階動量，AdaGrad在SGD基礎上加了二階動量。那麼把一階動量和二階動量都用起來，就是Adam了。

具體地，首先計算一階動量：

$m_t=\beta_1 m_{t-1}+(1-\beta_1)g_t$

然後，類似RMSProp/AdaDelta計算二階動量

$v_{t,i}=\beta_2 v_{t-1,i} + (1-\beta_2)g_{t,i}^2$

$V_t=diag(v_{t,i},v_{t,2},...,v_{t,d}) \in R^{d\times d}$

然後分別加上指數加權移動平均值的修正因子

$\hat m_t=\frac{m_t}{1-\beta_1^t}$

$\hat v_{t,i}=\frac{v_{t,i}}{1-\beta_2^t}$

$\hat V_t=diag(\hat v_{t,i},\hat v_{t,2},...,\hat v_{t,d}) \in R^{d\times d}$

最後，Adam的引數更新公式為：

$\Delta \theta_t=-\frac{\eta}{\sqrt{\hat V_t + \epsilon}}\cdot \hat m_t$

$\theta_{t+1} = \theta_t-\frac{\eta}{\sqrt{\hat V_t + \epsilon}}\cdot \hat m_t$

8。 Nadam

由於Adam沒有將Nesterov整合進來，而Nadam則是在Adam的基礎上將Nesterov整合進來，即Nadam=Nesterov+Adam。

具體思想如下：由於Nesterov的核心在於，計算當前時刻的梯度

時使用了“

未來梯度

”（往前走一步）

$\bigtriangledown J(\theta_t - \beta m_{t-1})$

，Nadam基於此提出了一種公式變形的思路，大意可以這樣理解：只要能在梯度計算中考慮到“

未來因素

”，就算是達到了Nesterov的效果。既然如此，就不一定非要在計算

時使用“

未來因素

”，可以在其他地方也考慮使用“

未來因素

”。

具體地，首先Nadam在Adam的基礎上將

$\hat m_t$

展開

$\theta_{t+1} =\theta_t-\frac{\eta}{\sqrt{{\hat V_t}+\epsilon}}\cdot \hat m_t =\theta_t-\frac{\eta}{\sqrt{{\hat V_t}+\epsilon}}\cdot (\frac{\beta_1 m_{t-1}}{1-\beta_1^t}+\frac{(1-\beta_1)g_t}{1-\beta_1^t})$

此時，如果將第

時刻的動量

$m_{t-1}$

用第

時刻的動量

近似代替的話，那麼就算引入了“

未來因素

”，所以將

$m_{t-1}$

替換成

即可得到Nadam的表示式

$\theta_{t+1} =\theta_t-\frac{\eta}{\sqrt{{\hat V_t}+\epsilon}}\cdot (\frac{\beta_1 m_{t}}{1-\beta_1^t}+\frac{(1-\beta_1)g_t}{1-\beta_1^t})=\theta_t-\frac{\eta}{\sqrt{{\hat V_t}+\epsilon}}\cdot (\frac{\beta_1 \hat m_{t}}{1-\beta_1^t}+\frac{(1-\beta_1)g_t}{1-\beta_1^t})$