AdaGrad（自适应梯度的缩写）是一种用于机器学习和深度学习的优化算法，它为每个参数单独调整学习率。与对所有参数应用单一学习率的标准随机梯度下降不同，AdaGrad根据每个参数的历史梯度平方和来缩放该参数的更新。这种逐参数自适应使得算法能够对不频繁出现的参数进行较大更新，而对频繁出现的参数进行较小更新，这在稀疏数据场景中尤为有用。AdaGrad由John Duchi、Elad Hazan和Yoram Singer于2011年提出，并已成为后续自适应优化器（如RMSProp和Adam）发展的基础方法。
AdaGrad的核心思想是为每个参数维护过去梯度平方的运行总和。在每次迭代中，参数的学习率除以该累积总和的平方根。这意味着具有较大历史梯度的参数获得较小的有效学习率，而具有较小或不频繁梯度的参数获得较大的有效学习率。梯度平方的累积是单调递增的，这导致有效学习率随时间衰减。这一特性在凸优化场景中有助于收敛，但在非凸问题中可能导致过度激进的衰减，这一局限性促使了后续算法的开发。
背景
机器学习中的优化通常涉及最小化一个由逐样本损失函数之和构成的目标函数。对于包含n个样本的训练集，经验风险由Q(w) = (1/n) Σ Q_i(w)给出，其中w是参数向量，Q_i是第i个样本的损失。标准梯度下降在每一步计算整个总和的梯度，当n很大时计算成本可能很高。随机梯度下降（SGD）则使用单个样本或小批量来近似梯度，降低了每次迭代的计算成本，但引入了噪声。20世纪50年代的Robbins-Monro算法为随机近似奠定了基础，SGD因其在大数据集上的高效性而成为机器学习中的常用方法。
在SGD中，更新规则为w := w - η ∇Q_i(w)，其中η是学习率。选择固定学习率通常不是最优的：过大的学习率可能导致发散，而过小的学习率则减缓收敛。像AdaGrad这样的自适应方法旨在通过根据优化景观的几何形状调整学习率来解决这一问题。AdaGrad的动机来自于观察到不同参数可能需要不同的步长，尤其是在具有稀疏特征的问题中，某些参数更新频率较低。
算法
AdaGrad通过维护一个对角矩阵G_t来修改SGD更新，其中每个对角元素是对应参数的过去梯度平方和。在时间步t，参数w_i的更新为：
w_i := w_i - (η / sqrt(G_{t,ii} + ε)) ∇Q_i(w_i)，
其中ε是一个小常数（例如1e-8），以避免除以零。累积的梯度平方G_{t,ii} = Σ_{τ=1}^{t} (∇Q_i(w_τ))^2。这可以写成向量形式：
w := w - η * diag(G_t + εI)^{-1/2} ∇Q(w)。
在实践中，该算法通常应用于小批量，其中梯度在训练样本的子集上计算。因此，逐参数学习率为η_t,i = η / sqrt(G_{t,ii} + ε)。由于G_t随时间增长，有效学习率下降，确保算法在进展过程中采取更小的步长。这与带有动量的SGD形成对比，后者累积梯度以在一致方向上加速。
数学性质
AdaGrad最初在凸优化的背景下进行分析。作者表明，对于凸函数，AdaGrad实现了渐近最优的在线学习遗憾界。具体来说，遗憾（衡量算法损失与事后最佳固定参数之间的累积差异）对于AdaGrad以O(√T)增长，匹配在线凸优化的下界。这优于具有固定学习率的标准SGD，后者可能需要仔细调整学习率调度。
关键见解在于AdaGrad自动适应特征空间的几何形状。在稀疏设置中，许多特征在大多数样本中为零，这些特征的累积梯度保持较小，允许在它们出现时进行较大更新。这使得AdaGrad在自然语言处理和其他具有高维稀疏输入的领域中特别有效。
然而，梯度平方的累积是单调递增的，这意味着学习率随时间衰减到零。在非凸问题中，例如训练深度神经网络，这可能导致算法过早停止学习。这一局限性导致了变体的开发，如RMSProp（使用平方梯度的移动平均而不是总和）和Adam（将自适应学习率与动量相结合）。
应用
AdaGrad已应用于各种机器学习任务，特别是涉及稀疏数据的任务。在自然语言处理中，它被用于训练基于词袋特征（每个文档由稀疏的词频向量表示）的模型。逐参数自适应允许稀有词获得较大更新，提高模型从罕见但信息丰富的特征中学习的能力。
在推荐系统中，AdaGrad被用于优化矩阵分解模型，其中用户和物品嵌入基于稀疏交互数据进行更新。该算法处理不同频率的用户-物品对的能力使其适用于此类设置。此外，AdaGrad已用于在线学习场景，其中数据顺序到达，模型必须快速适应。
尽管在许多深度学习应用中被更先进的优化器所取代，AdaGrad仍然是比较的基准，并在其属性有利的某些领域仍在使用。其影响在后来自适应方法的设计中显而易见，这些方法建立在逐参数学习率的思想之上。
局限性与扩展
AdaGrad的主要局限性是学习率单调递减。在深度学习中，损失景观是非凸的，这可能导致收敛缓慢或陷入较差的局部最小值。为解决这一问题，研究人员提出了几种扩展：
- RMSProp：由Geoffrey Hinton在其讲义中提出，RMSProp使用平方梯度的指数衰减平均，使学习率更灵活地适应。
- Adam：由Diederik Kingma和Jimmy Ba于2014年提出，Adam将RMSProp的移动平均与动量相结合，提供自适应学习率和动量。
- AdaDelta：由Matthew Zeiler开发，AdaDelta通过使用过去梯度的窗口消除了对学习率超参数的需求。
这些算法已成为训练深度神经网络的默认选择，但它们都源于AdaGrad引入的自适应梯度概念。
影响与遗产
AdaGrad对机器学习优化领域产生了持久影响。它是最早广泛采用逐参数学习率的算法之一，为一系列自适应优化器铺平了道路。其在凸设置中的理论保证为理解自适应方法提供了坚实基础。该算法经常在教科书和研究论文中被引用为优化历史上的关键发展。
在实践中，AdaGrad如今较少用于训练大规模深度学习模型，因为Adam及其变体往往表现更好。然而，对于特定问题（如具有稀疏特征的问题），它仍然是一个有用的工具，并且在机器学习课程中仍被教授为重要的概念性步骤。