AdaGrad/zh

Article
Topic area	optimization
Prerequisites	Stochastic gradient descent, Gradient, Loss function

概述

AdaGrad 是 Adaptive Gradient Algorithm（自適應梯度算法）的簡稱，是一種一階優化方法，它對每個參數獨立地調整學習率，按該參數所有歷史平方梯度之和的平方根的倒數來縮放更新量。該算法由 Duchi、Hazan 和 Singer 於 2011 年提出，是最早被廣泛使用的自適應學習率方法之一，也是 RMSProp、Adadelta 和 Adam 等現代優化器的直接前身。其核心想法是：高頻出現的特徵應獲得較小的更新，而罕見的特徵應獲得較大的更新，這對自然語言文本或點擊流等稀疏數據尤其有價值。

AdaGrad 介於普通的隨機梯度下降和用於訓練現代神經網絡的自適應優化器家族之間。其按參數自動縮放的特性減輕了調整學習率的負擔，但平方梯度的無界累積會使有效步長單調地趨向零；這一特性在凸優化問題中有時是可取的，但在深度網絡的訓練中往往會造成阻礙。如今 AdaGrad 很少作為深度學習的默認優化器，但它在教學上依然重要，並繼續出現在凸優化、在線學習以及高維稀疏回歸等場景中。

動機與直覺

在經典的隨機梯度下降（SGD）中，所有參數都使用同一個標量學習率進行更新。當不同參數需要不同更新幅度時，這種做法就會顯得彆扭。設想一個在詞嵌入上訓練的語言模型：像 "the" 這樣的常用詞的嵌入幾乎在每個小批量中都會收到梯度信號，而生僻詞的嵌入在整個周期里可能只會被觸及寥寥數次。對兩者使用同一個學習率必然要做出妥協：要小到能讓常用詞保持穩定，但又會因此過小，無法在生僻詞上取得有意義的進展。

AdaGrad 通過為每個參數賦予各自的學習率來解決這一問題，該學習率會根據參數已經接收到的梯度信號的多少而衰減。頻繁受到較大梯度作用的參數會被縮小步長；很少受到作用的參數則保留較大的步長。其結果是一種按坐標定製的隱式學習率退火，無需實踐者手動安排衰減計劃。

可以從幾何上理解這種效應。AdaGrad 通過過去梯度的外積累加器的逆平方根來近似實現對梯度的對角預處理。這是對 牛頓法等二階方法的廉價替代——後者使用 海森矩陣的逆作為預處理器。當牛頓法在高維問題中過於昂貴時，AdaGrad 提供了一種按坐標進行的近似，以每個參數多一個累加器的代價，捕獲了部分相同的尺度不變性收益。

公式化

設 $ \theta \in \mathbb{R}^d $ 為參數向量，$ g_t = \nabla_\theta L_t(\theta_{t-1}) $ 為第 $ t $ 步損失 $ L_t $ 的梯度。AdaGrad 維護一個按元素平方梯度的累計和

$ {\displaystyle G_t = \sum_{\tau=1}^{t} g_\tau \odot g_\tau} $

其中 $ \odot $ 表示按元素（Hadamard）乘積。參數更新為

$ {\displaystyle \theta_t = \theta_{t-1} - \frac{\eta}{\sqrt{G_t + \epsilon}} \odot g_t} $

其中 $ \eta $ 是一個全局步長（通常稱為基礎學習率），而 $ \epsilon $ 是一個很小的常數，通常取 $ 10^{-8} $，用於在第一步時防止除以零，並對累加器仍較小的參數的更新做衰減。平方根與除法均按元素進行。

等價地，若記 $ G_t = \mathrm{diag}(s_t) $，其中 $ s_t \in \mathbb{R}^d $ 為該累計和，則第 $ i $ 個坐標的更新為

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

原始論文給出了一種更一般的完整矩陣變體，其中 $ G_t $ 是完整的外積累加器 $ \sum_\tau g_\tau g_\tau^\top $，更新使用 $ G_t^{-1/2} $。完整矩陣變體具有更強的理論保證，但在實踐中很少使用，因為當 $ d $ 達到百萬乃至十億級別參數時，存儲並求逆 $ d \times d $ 的矩陣是不可行的。當從業者不加限定地說 "AdaGrad" 時，所指的就是上文描述的對角變體。

算法

對角變體的典型實現非常直接：

初始化：
  theta  := 初始参数
  s      := 0  （与 theta 形状相同的向量）
  eta    := 基础学习率（例如 0.01）
  eps    := 1e-8

对 t = 1, 2, ... 直到收敛：
  采样一个小批量并计算梯度 g_t
  s := s + g_t * g_t                # 按元素平方累加
  theta := theta - eta * g_t / (sqrt(s) + eps)

累加器 $ s $ 所需的內存與參數向量相同，因此與普通的SGD相比，AdaGrad 將優化器狀態翻了一倍。相比之下，Adam 大約需要三倍的參數內存，因為它同時跟蹤一階矩和二階矩的估計。

在 PyTorch 和 TensorFlow 等現代框架中，AdaGrad 以即插即用的優化器形式提供（torch.optim.Adagrad、tf.keras.optimizers.Adagrad），並提供可選的初始累加值、學習率衰減和權重衰減等選項。

收斂性與遺憾

AdaGrad 最初在在線凸優化框架下進行了分析。對於具有有界梯度的凸損失函數，對角變體可以獲得如下遺憾界：

$ {\displaystyle R(T) = \sum_{t=1}^{T} L_t(\theta_t) - \min_{\theta^*} \sum_{t=1}^{T} L_t(\theta^*) = O\left(\sqrt{T} \cdot \sum_{i=1}^{d} \sqrt{\sum_{t=1}^{T} g_{t,i}^2}\right).} $

關鍵在於：內部按坐標求和使得當梯度稀疏時，該界比對應的 SGD 的 $ O(\sqrt{dT}) $ 界緊得多，因為很少被激活的坐標對總和的貢獻很小。這正是 AdaGrad 在稀疏特徵問題上有優勢這一直覺的形式化表述。

對於非凸目標（包括大多數深度網絡），並不存在與之相當的全局保證，但按坐標的縮放仍然能帶來實際的預處理收益，尤其是在訓練早期、累加器尚未變大之前。

變體與後繼者

AdaGrad 對平方梯度的單調累積導致步長不斷縮小，這可能在模型尚未達到良好最優解之前就使訓練停滯。若干後繼算法直接針對這一問題：

• RMSProp（Tieleman 與 Hinton，2012）將累計和替換為平方梯度的指數移動平均 $ s_t = \rho s_{t-1} + (1-\rho) g_t \odot g_t $。這為有效學習率提供了下界，並在梯度幅度發生變化時恢復了進行較大更新的能力。
• Adadelta（Zeiler，2012）進一步發展了 RMSProp 的指數平均，做法是同時對過去參數更新的滑動平均進行歸一化，從而消除了作為超參數的全局學習率 $ \eta $。
• Adam（Kingma 與 Ba，2014）將 RMSProp 對平方梯度的滑動平均與對梯度本身的另一個滑動平均結合起來，在按參數縮放之外提供類似動量的行為。Adam 如今是深度學習領域佔主導地位的優化器。
• AdaGrad-Norm 使用所有參數共享的單個標量累加器 $ s_t = \sum_\tau \|g_\tau\|^2 $。這放棄了按參數的自適應，但分析起來更簡單，並且對非凸優化有清晰的收斂保證。

關於稀疏 AdaGrad 更新的另一條研究路線還產生了惰性變體——它們僅觸及與非零梯度坐標對應的累加器條目，這對超高維稀疏模型而言是一項重要的優化。

與其他優化器的比較

與普通的 SGD 相比，AdaGrad 在許多凸優化場景中消除了人工設計學習率調度的需要，並能優雅地處理稀疏梯度。它的主要缺點是累加器增長最終會導致停滯。

與 Adam 相比，AdaGrad 更簡單、超參數更少、內存佔用更小，但通常更慢，並且在訓練深度網絡時表現更差。Adam 的指數平均避免了停滯問題，其動量項有助於逃離損失景觀中狹窄的山谷。

與 牛頓法或 L-BFGS 等二階方法相比，AdaGrad 的代價要低得多，因為它只需要對角存儲和按元素的運算，但其預處理形式也要弱得多。

在實際應用中，AdaGrad 仍然出現在推薦系統、點擊率預測以及大規模邏輯回歸的生產環境中——這些場景中特徵高度稀疏，凸優化的形式化契合 AdaGrad 的理論優勢。Google 原始的 FTRL（Follow The Regularized Leader）廣告 CTR 預測算法與之關係密切，同樣採用了按坐標累積的思想。

局限性

AdaGrad 的標誌性局限在於有效學習率的單調衰減。由於 $ G_t $ 只會增長，步長 $ \eta / \sqrt{G_t + \epsilon} $ 只能縮小。在長時間的訓練運行中——尤其是在非凸問題中，模型在訓練後期需要做較大調整時——這種激進的退火會導致過早停滯。RMSProp 和 Adam 正是為了解決這一問題而設計的。

次要的問題是對基礎學習率 $ \eta $ 的敏感性。雖然 AdaGrad 降低了對每參數學習率縮放的敏感性，但它仍然對全局尺度敏感，$ \eta $ 選擇不當可能會在早期引發更新爆炸，或者使進展過於緩慢。

最後，AdaGrad 的預處理純粹是對角的：它無法考慮參數之間的相關性。在參數維度強耦合的問題中——例如出現在病態線性系統中的情形——AdaGrad 相對於經過良好調參的帶動量的 SGD 可能沒有明顯優勢。

應用

AdaGrad 在實際中最有力的立足點在於具有稀疏高維特徵的凸優化問題：

• 點擊率預測以及廣告和推薦系統中的其他大規模邏輯回歸模型。
• 稀疏自然語言處理模型，尤其是詞袋和 n-元分類器，其中大多數特徵在任意給定樣本上都為零。
• 詞嵌入訓練——在 word2vec 等早期實現中，罕見詞嵌入受益於較大的更新。
• 在線學習場景：數據按序到達，按坐標的自適應比精心設計的調度更重要。

對於現代深度學習工作負載而言，AdaGrad 在很大程度上已被 Adam、AdamW 及相關方法所取代，但它仍然是一個有用的教學入門，並對新的凸優化問題來說是一個合理的基線。