超越Adam，從適應性學習率家族出發解讀ICLR 2018高分論文

機器之心原創

作者：蔣思源

最近，ICLR 2018 高分論文討論了 Adam 等適應性學習率演算法的收斂性缺點，並提出了一種新的 Adam 變體。為此，我們從 AdaGrad 開始，依次分析了 AdaDelta、RMSProp 和 Adam 等適應性學習率演算法家族，並在最後結合該 ICLR 2018 高分論文討論 Adam 的非收斂性和修正的方法。

隨機梯度下降是當前訓練深度網路的主流方法，該方法通過在小批量數據上計算損失函數的梯度而迭代地更新權重與偏置項。特別的，SGD 的一類變體通過使用歷史梯度某種形式的範數而調整學習率取得了很大的成功，因為它們能針對不同的參數採用不同的學習率。一般來說，適應性學習率演算法的基本思想是若損失函數對於某個給定模型參數的偏導保持相同的符號，那麼學習率應該增加。這一類演算法第一個比較流行的是 AdaGrad（Duchi et al., 2011; McMahan & Streeter, 2010），該演算法要比一般的 SGD 演算法在性能上有顯著性的提升，尤其是當梯度比較稀疏或比較小的情況下。

儘管 AdaGrad 在稀疏梯度的情況下工作良好，但由於在更新中使用了所有的歷史梯度信息，所以該演算法在損失函數非凸和梯度比較密集的情況下會引起學習率的快速衰減。此外，模型的高維空間更進一步加劇了這種缺點，因此 AdaGrad 的性能也會受到很大的影響。為了解決這種問題，目前已經有許多研究者提出了 AdaGrad 方法的變體，如 RMSPROP（Tieleman & Hinton, 2012）、Adam（Kingma & Ba, 2015）、AdaDelta（Zeiler, 2012）和 NAdam（Dozat, 2016）等。它們都使用歷史梯度平方的指數移動均值來緩解學習率過快衰減的現象，這基本上就限制更新會更多地依賴於過去幾次迭代的梯度信息。

雖然這些演算法能成功地應用於一些實踐和開發中，但它們在一些環境下並不會起作用。例如我們通常會觀察到有一些小批量數據會提供較大的梯度，雖然這種批量非常少，但這些較大的梯度會提供非常多的下降信息，它們在指數移動均值中會存在和影響很長一段時間，因此也就造成了演算法收斂到一個比較差的最優解。

為了理解和分析這種局限性，Sashank J. Reddi、Satyen Kale 和 Sanjiv Kumar 等人發表了一篇 ICLR 2018 論文《ON THE CONVERGENCE OF ADAM AND BEYOND》。該論文被接收為 ICLR 2018 的 Oral 論文，且最終雙盲評分一直在前幾名。為了對該論文做一些簡要的分析與討論，我們會從基本的適應性學習率演算法開始，然後再進一步討論它們的局限性與修正方法。

其實適應性學習率方法早在 80 年代就有學者進行了一定的研究，Delta-bar-delta（Jacobs, 1988）這一啟發式方法基於很簡單的想法，即如果損失函數對於某個給定模型參數的偏導保持相同的符號，那麼學習率應該增加。如果損失函數對於該參數的偏導變換了符號，那麼學習率就應該減少。這種學習演算法只能適應於全批量梯度下降，而後 AdaGrad（Duchi et al., 2011）第一次將適應性學習率演算法的性能提升到頂尖的水平，並廣泛應用於帶有稀疏梯度的模型。

AdaGrad

AdaGrad 亦稱為適應性梯度（Adaptive Gradient），它允許學習率基於參數進行調整，而不需要在學習過程中人為調整學習率。AdaGrad 對具有較大梯度的參數相應地有一個快速下降的過程，而具有小梯度的參數在學習率上有相對較小的下降速度。因此，AdaGrad 成了稀疏數據如圖像識別和 NLP 的天然選擇。然而 AdaGrad 的最大問題在於，某些案例中的學習率會變得太小，學習率的單調下降也會使得網路停止學習過程。在經典的動量演算法和 Nesterov 中，加速梯度參數更新是對所有參數進行的，並且學習過程中的學習率保持不變。在 Adagrad 中，每次迭代中每個參數使用的都是不同的學習率。以下是 AdaGrad 的參數更新式：

如下偽代碼所示，AdaGrad 首先抽取 m 個訓練樣本和對應的樣本標註，然後基於這些樣本計算損失函數對特定參數的梯度。將該梯度的平方加入歷史梯度項 r，然後再以 1/sqrt(r) 縮放學習率，從而根據歷史梯度的大小為每個參數定製學習率，其中 δ 是為防止分母為零的常量。

AdaGrad 演算法最大的特點是將歷史梯度 L2 範數的倒數作為縮放學習率的因子。因此從直觀上來說，一直擁有較大梯度的參數處於較陡的位置，它離最終收斂還有一段距離，因此我們可以選擇較大的學習率而加快梯度下降的速度。而對於較小的梯度，它的位置相對而言比較平坦，且很可能處於接近收斂的範圍，因此我們需要減小學習率而更謹慎地搜索最優解。

AdaDelta

AdaDelta 使用短期歷史梯度的信息而縮放學習率，它類似經典的動量演算法累積歷史的更新而加速學習。AdaDelta 可以有效克服 AdaGrad 的學習率過快減少至零，因為它將累積歷史梯度信息的範圍限制在固定窗口 w 內，從而不再採用動量演算法累積所有歷史梯度的做法。在時間 t 計算的 E[g^2](t) 依賴於歷史梯度的信息和當前的梯度值。因此，該移動平均的計算可以表示為：

其中 γ 在實踐中通常設為 0.9 左右。我們可以將這種移動平均的計算方法與隨即梯度下降相結合，SGD 更新的表達式為：

Adagrad 的更新為：

使用歷史梯度的信息 E[g^2]_t 替換對角矩陣 G_i，得到

其中分母是梯度的平方根誤差，

用

替換先前更新規則中的學習率 α，得到

如上是 AdaDelta 的更新方式及簡單的推導。如以下偽代碼，其描述了 AdaDelta 的詳細計算與更新過程：

我們首先會初始化梯度與超參數，然後計算當前時間步某個參數的梯度，再如上 E[g^2] 所示的移動均值計算式獲取短期歷史梯度的信息。在利用歷史梯度的移動均值情況下，我們可以根據短期梯度信息為每個參數設計學習率。但正如論文 ON THE CONVERGENCE OF ADAM AND BEYOND 所述，這種方法可能在某些情況下只能收斂到次優點。

RMSProp

RMSProp 演算法（Hinton，2012）修改 AdaGrad 以在非凸情況下表現更好，它改變梯度累積為指數加權的移動平均值，從而丟棄距離較遠的歷史梯度信息。RMSProp 與 Adadelta 的移動均值更新方式十分相似：

RMSProp 的更新規則如下：

在 RMSProp 中，學習率需要除以梯度平方的指數衰減平均值以為不同的參數縮放學習率。

RMSProp 的標準式如下所示：

如上為 RMSProp 的標準演算法，首先我們需要初始化全局學習率和控制移動平均長度範圍的超參數 ρ。在演算法的循環體中，首先需要採樣一個批量的數據，並計算損失函數對所有參數的梯度而作為梯度向量。隨後根據超參數 ρ 決定需要遺忘的歷史梯度範圍，即計算指數移動均值，並儲存在變數 r 中。最後只需要利用歷史梯度信息縮放對應的學習率就能完成梯度下降，在這些計算過程中，⊙表示對應元素之間的乘積。

我們同樣可以結合 Nesterov 動量而提升經典 RMSProp 演算法的效果：

如上所示，前面的初始化會多一個動量係數 α。在循環體內，我們抽取一個批量的數據會先計算臨時的更新，也就是先在動量方向上更新一步。然後我們需要計算預更新後，該位置的梯度 g，並利用梯度 g 的平方與歷史梯度更新新的歷史梯度信息。在利用歷史梯度信息縮放學習率後，我們就能更新 Nesterov 動量的速度變數，且利用該變數最終更新參數。

RMSProp 是 Hinton 在公開課上提出的最優化演算法，其實它可以視為 AdaDelta 的特例。但實踐證明 RMSProp 有非常好的性能，它目前在深度學習中有非常廣泛的應用。

Adam

最後一種就是近來非常流行的 Adam 演算法，雖然 ON THE CONVERGENCE OF ADAM AND BEYOND 重點分析了 Adam 的收斂性缺點，但仍然不能否認它是目前最高效和「自動化」的最優化方法之一。下面我們會根據 Adam 的原論文簡要介紹該演算法。

Adam 演算法和傳統的隨機梯度下降不同。隨機梯度下降保持單一的學習率（即 alpha）更新所有的權重，學習率在訓練過程中並不會改變。而 Adam 通過計算梯度的一階矩估計和二階矩估計而為不同的參數設計獨立的自適應性學習率。

Adam 演算法的提出者描述其為兩種隨機梯度下降擴展式的優點集合，即：

適應性梯度演算法（AdaGrad）為每一個參數保留一個學習率以提升在稀疏梯度（即自然語言和計算機視覺問題）上的性能。

均方根傳播（RMSProp）基於權重梯度最近量級的均值為每一個參數適應性地保留學習率。這意味著演算法在非穩態和在線問題上有很有優秀的性能。

Adam 演算法同時獲得了 AdaGrad 和 RMSProp 演算法的優點。Adam 不僅如 RMSProp 演算法那樣基於一階矩均值計算適應性參數學習率，它同時還充分利用了梯度的二階矩均值（即有偏方差/uncentered variance）。具體來說，演算法計算了梯度的指數移動均值（exponential moving average），超參數 beta1 和 beta2 控制了這些移動均值的衰減率。

移動均值的初始值和 beta1、beta2 值接近於 1（推薦值），因此矩估計的偏差接近於 0。該偏差通過首先計算帶偏差的估計而後計算偏差修正後的估計而得到提升。

如下偽代碼展示了 Adam 的基本演算法：

如上演算法所述，在確定了參數α、β1、β2 和隨機目標函數 f(θ) 之後，我們需要初始化參數向量、一階矩向量、二階矩向量和時間步。然後當參數θ沒有收斂時，循環迭代地更新各個部分。即時間步 t 加 1、更新目標函數在該時間步上對參數θ所求的梯度、更新偏差的一階矩估計和二階原始矩估計，再計算偏差修正的一階矩估計和偏差修正的二階矩估計，然後再用以上計算出來的值更新模型的參數θ。

該演算法的核心是 m_t hat 除以 sqrt(v_t hat)，其實它可以看作一種信噪比，即演算法對 m_t hat 是否符合真實梯度方向存在的不確定性。若該比值很小，表示 m_t hat 符合真實梯度方向有很大的不確定性，從而令有效步長接近於 0，令目標函數收斂。

上圖偽代碼為展現了 Adam 演算法的基本步驟。假定 f(θ) 為雜訊目標函數：即關於參數θ可微的隨機標量函數。我們對怎樣減少該函數的期望值比較感興趣，即對於不同參數θ，f 的期望值 E[f(θ)]。其中 f1(θ), ..., , fT (θ) 表示在隨後時間步 1, ..., T 上的隨機函數值。這裡的隨機性來源於隨機子樣本（小批量）上的評估和固有的函數雜訊。而表示 f_t(θ) 關於θ的梯度，即在實踐步驟 t 下 ft 對θ的偏導數向量。

該演算法更新梯度的指數移動均值（m_t）和平方梯度（v_t），而參數 β_1、β_2 ∈ [0, 1) 控制了這些移動均值（moving average）指數衰減率。移動均值本身使用梯度的一階矩（均值）和二階原點矩（有偏方差）進行估計。然而因為這些移動均值初始化為 0 向量，所以矩估計值會偏差向 0，特別是在初始時間步中和衰減率非常小（即β接近於 1）的情況下是這樣的。不過初始化偏差很容易抵消，因此我們可以得到偏差修正（bias-corrected）的估計 m_t hat 和 v_t hat。此外，m_t 和 v_t 可以通過數學歸納法求出對應的偏差修正項。

注意演算法的效率可以通過改變計算順序而得到提升，例如將偽代碼最後三行循環語句替代為以下兩個：

在這篇 ICLR 2018 的 Oral 論文中，研究者分析了這些基於指數移動均值方法的缺點，並嚴格地證明了少數較大梯度會影響收斂的效果。限制更新只依賴於少數歷史梯度確實會引起顯著的收斂性問題，該論文的作者也明確表明他們該論文的主要貢獻為：

通過提供一個簡單的凸優化問題作為案例來說明 RMSPROP 和 ADAM 中的指數移動均值會如何導致演算法不收斂，即 RMSPROP 和 ADAM 在該案例中不會如同動量法那樣收斂到相對最優解。該分析很容易擴展到其它使用指數移動均值的最優化方法，如 AdaDelta 和 NAdam。實際上，該分析足夠靈活以擴展到更一般的情況，即那些根據固定窗口大小而採用平均梯度的演算法，這些演算法一般會採用窗口範圍內的梯度信息而拋棄窗口外的梯度信息。但是該論文並沒有討論這些擴展情況，因而分析將變得更加明晰。

本論文的分析結果表明，為了保證收斂性，優化演算法必須具有歷史梯度的「長期記憶」。具體而言，作者們指出了 Kingma & Ba (2015) 關於 Adam 演算法收斂性證明的一個問題。為了解決這個問題，他們提出了一個 Adam 的新變體，它依賴於歷史梯度的長期記憶，且和原 Adam 演算法有相同的計算時和空間要求。Sashank 等人最後基於 Kingma & Ba (2015) 的分析展示了該新變體的收斂性分析。

Sashank 等人還對該變體進行了初步的實證研究，並表明它在常見機器學習問題中有相似或更優秀的性能。

以下是詳細的論文內容：

論文地址：https://openreview.net/pdf?id=ryQu7f-RZ

近來提出的幾種隨機優化方法已經成功地應用於深度網路的訓練，如 RMSPROP、ADAM、ADADELTA 和 NADAM 等方法，它們都是基於使用前面迭代所產生梯度平方的指數滑動平均值，在對該滑動平均值取平方根後用於縮放當前梯度以更新權重。根據經驗觀察，這些演算法有時並不能收斂到最優解（或非凸條件下的臨界點）。研究者證明了導致這樣問題的一個原因是這些演算法中使用了指數滑動平均（exponential moving average）操作。本論文提供了一個簡單的凸優化案例，其中 ADAM 方法並不能收斂到最優解。此外，研究者還描述了過去文獻中分析 ADAM 演算法所存在的精確問題。他們的分析表明，收斂問題可以通過賦予這些演算法對前面梯度的「長期記憶」能力而得到解決。因此該論文提出了一種 ADAM 演算法的新變體，其不僅解決了收斂問題，同時還提升了經驗性能。

在論文的第二章節中，研究者們重點討論了一般適應性方法和基於指數移動均值的適應性方法的表述：

一般適應性方法

原作者為適應性方法提供了一個通用性框架，它展示了不同適應性方法之間的區別，並有利於我們理解 Adam 等方法的缺陷。以下演算法 1 給出了一般適應性框架的偽代碼，該演算法仍然非常抽象，因為「均值」函數φ_t 和 ψ_t 並沒有明確指定。其中φ_t 為 d 維向量，而ψ_t 為 d*d 維正定矩陣。為了便於展示，作者將 α_t 設為下降步大小，將 α_t * V_t^(-1/2) 設為演算法的學習率。此外，作者將演算法 1 封裝的適應性方法限制為對角方差矩陣，即 V_t = diag(v_t)。我們發現因為φ_t(g_1, . . . , g_t) = g_t 、 ψ_t(g_1, . . . , g_t) = I，標準的隨即梯度下降會失效，其中對於所有的 t ∈ [T]，α_t = α/sqrt(t)。

儘管縮減下降步長是演算法收斂的先決條件，但如此暴力的學習率衰減方式會典型地收斂到較差的解，因此它會有較差的經驗性能。適應性方法的關鍵思想是選擇適當的均值函數而實現優良的收斂性。例如推動新研究的第一個適應性學習率演算法 Adagrad（Duchi et al., 2011）使用以下均值的函數：

這和 SGD 的α_t = α/sqrt(t) 不一樣，Adagrad 使用更加優秀的衰減策略，即對於 j ∈ [d]，α/sqrt(∑sqre(g^2))。當梯度是稀疏的情況下，演算法的收斂性能得到非常大的提升（Duchi et al. 2011），這在一些非稀疏的梯度設定中也能獲得很大的提升。

基於指數移動均值的適應性方法

基於指數移動均值的 AdaGrad 變體在深度學習社區中非常流行，RMSProp、Adam、NAdam 和 AdaDelta 都是這種變體的先驅研究。它們和 AdaGrad 最大的區別就是使用指數移動均值作為函數ψ_t，而不是使用簡單的均值函數。Adam 是最流行的一種變體，它使用的均值函數如下：

Adam 的非收斂性

根據前面章節的問題設定，我們將在本章節討論基於指數移動均值的 Adam 優化演算法的基本缺點。該論文的研究者展示了 Adam 即使在簡單的一維凸問題上都有可能不能收斂到最優解。這些不收斂的案例與（Kingma & Ba, 2015）聲明的收斂性相矛盾，主要的問題在於以下表達式的數值：

該數值基本上衡量了自適應學習率的倒數相對於時間的變化趨勢。一個關鍵點是，SGD 和 AdaGrad 對於所有 t ∈ [T] 都有Γ_t?0，這只是從 SGD 和 AdaGrad 的更新規則推導而出。特別的，這些演算法的更新規則並不會導致學習率的增加，即「non-increasing」學習率。然而，這對於其它如 Adam 和 RMSProp 等基於指數移動均值的方法是不成立的，即對於 t ∈ [T]，Γ_t 可能是不確定的。研究者們證明了這種違反正定性的屬性將導致 Adam 和 RMSProp 出現不期望的收斂情況。若我們考慮以下 F = [?1, 1] 的簡單線性函數序列：

其中 C>2。對於這個函數序列，我們很容易了解到 x=-1 提供了最小的回退。以下結果表明，當 β_1 = 0 和 β_2 = 1/(1 + C 2 ) 時，Adam 收斂於 x = +1 的高度次優解。直觀上的推理如下，該演算法每三步會獲取一個較大的梯度 C，其它兩步則會觀察到梯度-1 而導致錯誤的方向。較大的梯度 C 不能抵消這種影響，因為對於給定的 β_2 值，x 幾乎只會以常量 C 來縮小，因此演算法只能收斂到 1 而不是-1。

在該章節的後面部分和附錄中，研究者對這一非收斂現象進行了更形式化和細緻地分析。

一種新型指數移動均值方法：AMSGRAD

在這一章節中，Sashank 等研究者開發了一種新型指數移動均值變體，並提供了它的收斂性分析。他們的目標是設計一種保證收斂性的新策略，且能同時保留 Adam 和 AMSProp 的優勢。為了更好地理解這種演算法，我們需要重新審視表達式（2）中的 Γ_t。對於 Adam 和 RMSProp，該變數的數值仍然可能為負。Adam 原論文錯誤地假設 Γ_t 為半正定，這一錯誤在該論文的附錄 D 有詳細討論。首先，研究者會修正這些演算法以滿足額外的約束。隨後，我們會探索新的方法以令 Γ_t 在給定隨時間 t 而改變 β_1 和 β_2 的情況下為半正定。

與 Adam 相比，AMSGrad 使用較小的學習率，但只要Γ_t 為半正定，那麼它就保留了緩慢減弱歷史梯度對學習率的影響這一直觀屬性。演算法 2 展示了 AMSGrad 的偽代碼，它與 Adam 的關鍵不同點就是它會保留所有 v_t 的最大值到當前時間步，並使用該最大值歸一化梯度的移動均值，而不是使用 Adam 中的 v_t。通過這樣的修正，AMSGrad 可以保持非遞增的下降步大小，並避免了 Adam 和 RMSProp 的缺陷，即對於常數 β_2 和所有 t ∈ [T] 都有 Γ_t?0。此外在演算法 2 中，實踐上會典型地使用常數 β_1t，而實際證明要求一個遞減的方案來保證收斂性。

實驗

圖 2：ADAM 和 AMSGRAD 演算法在 Logistic 回歸、前饋神經網路和 CIFARNET 上的性能對比。第一行的左圖與中圖表示 ADAM 和 AMSGRAD 演算法在 Logistic 回歸的性能，第一行右圖表示它們在一層前饋神經網路和 MNIST 數據集的訓練損失。第二行表示兩種優化方法在 CIFARNET 的訓練損失與測試損失。

本文為機器之心原創，轉載請聯繫本公眾號獲得授權。

------------------------------------------------

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！