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 及相关方法所取代，但它仍然是一个有用的教学入门，并对新的凸优化问题来说是一个合理的基线。